devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

通俗易懂讲区间问题：前缀和数组、差分数组、线段树、树状数组（完结）_区间查询前缀和树状数组差分数组线段树

作者：很楠不爱3 | 2024-05-31 20:40:26

赞

踩

区间查询前缀和树状数组差分数组线段树

前缀和数组、差分数组、线段树、树状数组均用于处理区间问题，但有不同应用场景

  1. 前缀和数组：用于处理 连续多次取区间和 操作的情况，取区间和期间不能对原数组进行区间增减数操作

  2. 差分数组：用于处理 多次区间增减数操作，最后读取一次区间和（即修改期间读取不频繁） 操作的情况

  3. 线段树：用于处理 多次区间增减数操作，期间多次读取区间和（即修改期间读取频繁） 操作的情况

  4. 树状数组：用于处理 多次区间增减数操作，期间多次读取区间和（即修改期间读取频繁） 操作的情况，同线段树的情况、但树状数组更加简单且不支持区间更新，线段树支持区间更新但编码复杂

一、前缀和数组（一维）

在学习之前，千万不要忘记何时使用前缀和数组

前缀和数组：用于处理 连续多次取区间和 操作的情况，取区间和期间不能对原数组进行区间增减数操作

具体思想：

1. 求前缀和数组

假定原数组arr，前缀和数组prefixArr，当前讨论位置为i

那么有prefixArr[i]=arr[i]+arr[i-1]+arr[i-2]+......+arr[0]（即i位置及之前所有数累加和==>前缀 和）

由于prefixArr[i-1]=arr[i-1]+arr[i-2]+......+arr[0]

因此化简原式：prefixArr[i]=prefixArr[i-1]+arr[i]

2. 求区间和

设求[i,j]（j>i）区间的区间和

即求arr[i]+arr[i+1]+......+arr[j-1]+arr[j]

由于prefixArr[j]=arr[j]+arr[j-1]+arr[j-2]+......arr[0]，prefixArr[i-1]=arr[i-1]+arr[i-2]+arr[i-3]+......+arr[0]

因此所求区间和为prefixArr[j]-prefixArr[i-1]

简单来说如下：

红色区域为原数组，黄色区域为所求部分（区间和），那么我们先求蓝色区域与绿色区域（前缀和），再相减就得到了黄色区域

3. 代码如下

  1.  
  2. public class PrefixArr {
  3.     public static void main(String[] args) {
  4.         //获取数组
  5.         int[] arr = getArr(10);
  6.         for (int i = 0; i < arr.length; i++) {
  7.             System.out.print(arr[i] + " ");
  8.         }
  9.         System.out.println();
  10.         //前缀数组
  11.         int[] prefixArr = new int[arr.length];
  12.         prefixArr[0] = arr[0];
  13.         for (int i = 1; i < arr.length; i++) {
  14.             prefixArr[i] = prefixArr[i - 1] + arr[i];
  15.         }
  16.         //获取[i,j]区间的数
  17.         int i = 3;
  18.         int j = 5;
  19.         int ijNum = prefixArr[j] - prefixArr[i - 1];
  20.         System.out.println("ijNum: " + ijNum);
  21.     }
  22.  
  23.     private static int[] getArr(int len) {
  24.         int[] arr = new int[len];
  25.         for (int i = 0; i < arr.length; i++) {
  26.             arr[i] = (int) (Math.random() * 9 + 1);
  27.         }
  28.         return arr;
  29.     }
  30. }

二、差分数组（一维）

在学习之前，千万不要忘记何时使用差分数组

差分数组：用于处理 多次区间增减数操作，最后读取一次区间和（即修改期间读取不频繁） 操作的情况

具体思想：

1. 初始化差分数组

假定原数组arr，差分数组diff，注意差分数组diff的长度要比原数组长度多1（或者在区间修改时进行判断，这点在后面会提到）；差分数组所有位置初始为0

2. 接下来进行区间修改

因为差分数组是用于多次区间加减数操作后读取一次的情况，这里进行模拟区间增减数

如果要求在区间[i,j]每个数上增加数value，那么规定修改差分数组diff[i]+value,diff[j+1]-value。从这里可以知道为什么diff数组的长度需要比原数组多1，或者在区间修改的时候进行判断，防止数组越界

3. 通过差分数组获取更新值后的 更新数组

定理：差分数组的前缀和是更新数组，更新数组的含义是在[i,j]区间加value，那么更新数组下标从i到j都为value

证明：

设已有差分数组diff，更新数组update，在区间[i,j]每个数上添加value值，其余位置不更新

根据规定有：diff[i]=diff[i]+value=0+value=value，diff[j+1]=diff[j+1]-value=0-value=-value

那么现在求diff的前缀和数组prefix

prefix[0]=diff[0]=0

prefix[1]=diff[0]+diff[1]=prefix[0]+diff[1]=0

prefix[i]=diff[0]+diff[1]+......+diff[i-1]+diff[i]=value

prefix[i+1]=diff[0]+diff[1]+diff[2]+......+diff[i]+diff[i+1]=prefix[i]+diff[i+1]=value+0=value

......

prefix[j]=prefix[j-1]+diff[j]=value+0=value

prefix[j+1]=prefix[j]+diff[j+1]=value+(-value)=0

所以差分数组前缀和数组就是更新数组update

i位置加value会影响 更新数组 i位置以后的位置加value（由于更新数组是差分数组的前缀和），即蓝色和黄色的区域都加value

j+1位置减value会影响 更新数组 j+1位置以后的位置减value（由于更新数组是差分数组的前缀和），即黄色区域减value

所以在经过修改差分数组diff[i]+value,diff[j+1]-value后再求差分数组前缀和数组就是更新数组

4. 代码如下

  1.  
  2. public class DiffArr {
  3.     public static void main(String[] args) {
  4.         //获取数组
  5.         int[] arr = getArr(10);
  6.         for (int i = 0; i < arr.length; i++) {
  7.             System.out.print(arr[i] + " ");
  8.         }
  9.         System.out.println();
  10.         //差分数组
  11.         int[] diff = new int[arr.length + 1];
  12.         //区间修改，如在区间[i,j]加v  <==>d[L]+v,d[R+1]-v 因此差分数组要多一个数
  13.         addRange(2, 4, diff, 10);
  14.         addRange(1, 9, diff, -5);
  15.         //差分数组的前缀和是更新区域的更新值
  16.         for (int i = 1; i < diff.length; i++) {
  17.             diff[i] = diff[i] + diff[i - 1];
  18.         }
  19.         //更新后的数组是原数组+更新数组
  20.         for (int i = 0; i < arr.length; i++) {
  21.             System.out.print((arr[i]+diff[i]) + " ");
  22.         }
  23.     }
  24.  
  25.     public static void addRange(int i, int j, int[] diff, int value) {
  26.         diff[i] += value;
  27.         diff[j + 1] -= value;
  28.     }
  29.  
  30.     private static int[] getArr(int len) {
  31.         int[] arr = new int[len];
  32.         for (int i = 0; i < arr.length; i++) {
  33.             arr[i] = (int) (Math.random() * 9 + 1);
  34.         }
  35.         return arr;
  36.     }
  37. }

三、前缀和数组（二维）

具体思想：

1. 求二维前缀和

定义：二维前缀和是指(0,0)位置与(i,j)围成矩阵内数的和

假定原二维数组为arr，二维前缀和数组prefixArr，求(i,j)位置的前缀和

prefixArr[i][j]=(arr[0][0]+arr[0][1]+arr[0][2]+......+arr[0][j])+(arr[1][0]+arr[1][1]+arr[1][2]+......+arr[1][j])+......+(arr[i][0]+arr[i][1]+arr[i][2]+......+arr[i][j])

由于

prefixArr[i-1][j] = (arr[0][0]+arr[0][1]+arr[0][2]+......+arr[0][j])+(arr[1][0]+arr[1][1]+arr[1][2]+......+arr[1][j])+......+(arr[i-1][0]+arr[i-1][1]+arr[i-1][2]+......+arr[i-1][j])

prefixArr[i][j-1] = (arr[0][0]+arr[0][1]+arr[0][2]+......+arr[0][j-1])+(arr[1][0]+arr[1][1]+arr[1][2]+......+arr[1][j-1])+......+(arr[i][0]+arr[i][1]+arr[i][2]+......+arr[i][j-1])

prefixArr[i-1][j-1] = (arr[0][0]+arr[0][1]+arr[0][2]+......+arr[0][j-1])+(arr[1][0]+arr[1][1]+arr[1][2]+......+arr[1][j-1])+......+(arr[i-1][0]+arr[i-1][1]+arr[i-1][2]+......+arr[i-1][j-1])

因此化简：prefixArr[i][j]=prefixArr[i-1][j]+prefixArr[i][j-1] -prefixArr[i-1][j-1]+arr[i][j]

prefixArr[i-1][j]=蓝色+黄色

prefixArr[i][j-1]=绿色+黄色

prefixArr[i-1][j-1]=黄色

prefixArr[i][j]=红色+蓝色+黄色+绿色=（红色）+（蓝色+黄色）+（绿色+黄色）-黄色=arr[i][j]+prefixArr[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]

2. 求区间和 (i,j)->(m,n)的区间和

根据图很容易看出：prefixArr[m][n] - prefixArr[i - 1][n] - prefixArr[m][j - 1] + prefixArr[i - 1][j - 1];

3. 代码如下

  1.  
  2. public class PrefixArr2Dim {
  3.     public static void main(String[] args) {
  4.         int[][] arr = getArr2Dim(8, 8);
  5.         for (int i = 0; i < arr.length; i++) {
  6.             for (int j = 0; j < arr[i].length; j++) {
  7.                 System.out.print(arr[i][j] + " ");
  8.             }
  9.             System.out.println();
  10.         }
  11.         System.out.println("==========================");
  12.         //求前缀和
  13.         int[][] prefixArr = new int[arr.length][arr[0].length];
  14.         prefixArr[0][0] = arr[0][0];
  15.         //第一行与第一列需要特殊处理
  16.         for (int j = 1; j < arr[0].length; j++) {
  17.             prefixArr[0][j] = prefixArr[0][j - 1] + arr[0][j];
  18.         }
  19.         for (int i = 1; i < arr.length; i++) {
  20.             prefixArr[i][0] = prefixArr[i - 1][0] + arr[i][0];
  21.         }
  22.         for (int i = 1; i < arr.length; i++) {
  23.             for (int j = 1; j < arr[i].length; j++) {
  24.                 prefixArr[i][j] = prefixArr[i - 1][j] + prefixArr[i][j - 1] - prefixArr[i - 1][j - 1] + arr[i][j];
  25.             }
  26.         }
  27.         for (int i = 0; i < prefixArr.length; i++) {
  28.             for (int j = 0; j < prefixArr[i].length; j++) {
  29.                 System.out.print(prefixArr[i][j] + " ");
  30.             }
  31.             System.out.println();
  32.         }
  33.         System.out.println("==========================");
  34.         //求区间和 [i,j]与[m,n]的区间和
  35.         int i = 2, j = 3, m = 7, n = 6;
  36.         int sum = prefixArr[m][n] - prefixArr[i - 1][n] - prefixArr[m][j - 1] + prefixArr[i - 1][j - 1];
  37.         System.out.println(sum);
  38.     }
  39.  
  40.     public static int[][] getArr2Dim(int firstDim, int secondDim) {
  41.         int[][] arr = new int[firstDim][secondDim];
  42.         for (int i = 0; i < arr.length; i++) {
  43.             for (int j = 0; j < arr[i].length; j++) {
  44.                 arr[i][j] = (int) (Math.random() * 9 + 1);
  45.             }
  46.         }
  47.         return arr;
  48.     }
  49. }

四、差分数组（二维）

1. 首先要理解：以下为diff差分数组

如果在(i,j)位置加value值，那么会影响第四象限的所有位置的值加value，如图：

所以如果现在要在(i,j)->(m,n)矩阵区域加value，如图蓝色区域

(i,j)添加value，会影响 蓝色+橙色+绿色+红色 区域

(i,n+1)添加value，会影响 橙色+红色 区域

(m+1,j)添加value，会影响 绿色+红色 区域

(m+1,n+1)添加value，会影响 红色 区域

所以要只让蓝色区域加value，要在(i,j)位置加value，(i,n+1)位置减value，(m+1,j)位置减value，(m+1,n+1)位置加value

2. 差分数组求前缀和是更新数组

3. 更新数组加上原数组是更新修改后的数组

4.代码

  1.  
  2. public class DiffArr2Dim {
  3.     public static void main(String[] args) {
  4.         //获取原数组
  5.         int[][] arr = getArr2Dim(7, 7);
  6.         //输出
  7.         for (int i = 0; i < arr.length; i++) {
  8.             for (int j = 0; j < arr[i].length; j++) {
  9.                 System.out.print(arr[i][j]+" ");
  10.             }
  11.             System.out.println();
  12.         }
  13.         System.out.println("============================");
  14.         //求差分数组
  15.         int[][] diff = new int[arr.length + 1][arr[0].length + 1];
  16.         addRegion(diff, 0, 0, 2, 3, 10);
  17.         addRegion(diff, 1, 1, 5, 6, -10);
  18.         //求差分数组前缀和
  19.         int[][] prefixArr = new int[arr.length][arr[0].length];
  20.         prefixArr[0][0] = diff[0][0];
  21.         //第一行与第一列特殊处理
  22.         for (int j = 1; j < arr[0].length; j++) {
  23.             prefixArr[0][j] = prefixArr[0][j - 1] + diff[0][j];
  24.         }
  25.         for (int i = 1; i < arr.length; i++) {
  26.             prefixArr[i][0] = prefixArr[i - 1][0] + diff[i][0];
  27.         }
  28.         //其余位置
  29.         for (int i = 1; i < arr.length; i++) {
  30.             for (int j = 1; j < arr[i].length; j++) {
  31.                 prefixArr[i][j] = prefixArr[i - 1][j] + prefixArr[i][j - 1] - prefixArr[i - 1][j - 1] + diff[i][j];
  32.             }
  33.         }
  34.         //输出
  35.         for (int i = 0; i < prefixArr.length; i++) {
  36.             for (int j = 0; j < prefixArr[i].length; j++) {
  37.                 System.out.print(prefixArr[i][j]+" ");
  38.             }
  39.             System.out.println();
  40.         }
  41.         System.out.println("============================");
  42.         //输出修改后的数组
  43.         for (int i = 0; i < arr.length; i++) {
  44.             for (int j = 0; j < arr[i].length; j++) {
  45.                 System.out.print((arr[i][j]+diff[i][j])+" ");
  46.             }
  47.             System.out.println();
  48.         }
  49.     }
  50.  
  51.     private static void addRegion(int[][] diff, int i, int j, int m, int n, int value) {
  52.         diff[i][j] += value;
  53.         diff[i][n + 1] -= value;
  54.         diff[m + 1][j] -= value;
  55.         diff[m + 1][n + 1] += value;
  56.     }
  57.  
  58.     public static int[][] getArr2Dim(int firstDim, int secondDim) {
  59.         int[][] arr = new int[firstDim][secondDim];
  60.         for (int i = 0; i < arr.length; i++) {
  61.             for (int j = 0; j < arr[i].length; j++) {
  62.                 arr[i][j] = (int) (Math.random() * 9 + 1);
  63.             }
  64.         }
  65.         return arr;
  66.     }
  67. }

五、线段树

在学习之前，千万不要忘记何时使用线段树

线段树：用于处理 多次区间增减数操作，期间多次读取区间和（即修改期间读取频繁） 操作的情况

具体思想：

  1. 将区间的增减更新任务揽住，不下发

  2. 当有新的任务到来，下发一层

  3. 由于使用树状区间结构揽住任务，每次任务到来时只需要log(N)的时间复杂度

  4. 叶子结点代表原数组arr中的某一索引位置的值，内部节点代表原数组arr中某一范围的区间和


  1. public static class SegmentTree {
  2.     private int MAXN;//最大长度
  3.     private int[] arr;//存储原数组，但下标从1开始
  4.     private int[] sum;//存储区间和
  5.     private int[] lazy;//存储揽住增加的值
  6.     private int[] change;//存储揽住更新的值
  7.     private boolean[] update;//标记change是否是更新
  8.  
  9.     public SegmentTree(int[] origin) {
  10.         MAXN = origin.length + 1;
  11.         arr = new int[MAXN];
  12.         for (int i = 1; i < MAXN; i++) {
  13.             arr[i] = origin[i - 1];
  14.             sum = new int[MAXN << 2];
  15.             lazy = new int[MAXN << 2];
  16.             change = new int[MAXN << 2];
  17.             update = new boolean[MAXN << 2];
  18.         }
  19.     }
  20.  
  21.     //rt位置的sum（也就是rt节点）=rt左孩子的sum+rt右孩子的sum
  22.     private void pushUp(int rt) {
  23.         sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  24.     }
  25.  
  26.     // 初始化阶段：把sum数组，填好
  27.     // 代表当前sum的rt位置=arr的l-r范围的和
  28.     public void build(int l, int r, int rt) {
  29.         if (l == r) {
  30.             sum[rt] = arr[l];
  31.             return;
  32.         }
  33.  
  34.         int mid = (l + r) >> 1;
  35.         //构造左
  36.         build(l, mid, rt << 1);
  37.         //构造右
  38.         build(mid + 1, r, rt << 1 | 1);
  39.         //求和
  40.         pushUp(rt);
  41.     }
  42.  
  43.     //在L-R范围上加C
  44.     //l-r，当前rt位置的格子代表的范围
  45.     public void add(
  46.             int L, int R, int C,
  47.             int l, int r,
  48.             int rt
  49.     ) {
  50.         if (L <= l && R >= r) {
  51.             sum[rt] += C * (r - l + 1);
  52.             lazy[rt] += C;
  53.             return;
  54.         }
  55.         //任务没有全包
  56.         int mid = (l + r) >> 1;
  57.         pushDown(rt, mid - l + 1, r - mid);
  58.         //需要发给左边再发
  59.         if (L <= mid) {
  60.             add(L, R, C, l, mid, rt << 1);
  61.         }
  62.         //需要发给右边再发
  63.         if (R > mid) {
  64.             add(L, R, C, mid + 1, r, rt << 1 | 1);
  65.         }
  66.         //左右都更新好，现在更新当前
  67.         pushUp(rt);
  68.     }
  69.  
  70.     public void update(
  71.             int L, int R, int C,
  72.             int l, int r, int rt
  73.     ) {
  74.         if (L <= l && R >= r) {
  75.             update[rt] = true;
  76.             change[rt] = C;
  77.             sum[rt] = C * (r - l + 1);
  78.             lazy[rt] = 0;
  79.             return;
  80.         }
  81.  
  82.         //揽不住
  83.         int mid = (l + r) >> 1;
  84.         pushDown(rt, mid - l + 1, r - mid);
  85.         //需要发给左边再发
  86.         if (L <= mid) {
  87.             update(L, R, C, l, mid, rt << 1);
  88.         }
  89.         //需要发给右边再发
  90.         if (R > mid) {
  91.             update(L, R, C, mid + 1, r, rt << 1 | 1);
  92.         }
  93.         //左右都更新好，现在更新当前
  94.         pushUp(rt);
  95.     }
  96.  
  97.     //ln->左孩子范围的数量，rn->右孩子范围的数量
  98.     private void pushDown(int rt, int ln, int rn) {
  99.         if (update[rt]) {
  100.             update[rt << 1] = true;
  101.             update[rt << 1 | 1] = true;
  102.             change[rt << 1] = change[rt];
  103.             change[rt << 1 | 1] = change[rt];
  104.             lazy[rt << 1] = 0;
  105.             lazy[rt << 1 | 1] = 0;
  106.             sum[rt << 1] = change[rt] * ln;
  107.             sum[rt << 1 | 1] = change[rt] * rn;
  108.             update[rt] = false;
  109.         }
  110.         if (lazy[rt] != 0) {
  111.             lazy[rt << 1] += lazy[rt];
  112.             sum[rt << 1] += lazy[rt] * ln;
  113.  
  114.             lazy[rt << 1 | 1] += lazy[rt];
  115.             sum[rt << 1 | 1] += lazy[rt] * rn;
  116.  
  117.             lazy[rt] = 0;
  118.         }
  119.     }
  120.  
  121.     public long query(int L, int R, int l, int r, int rt) {
  122.         if (L <= l && R >= r) {
  123.             return sum[rt];
  124.         }
  125.         int mid = (l + r) >> 1;
  126.         pushDown(rt, mid - l + 1, r - mid);
  127.         long ans = 0;
  128.         if (L <= mid) {
  129.             ans += query(L, R, l, mid, rt << 1);
  130.         }
  131.         if (R > mid) {
  132.             ans += query(L, R, mid + 1, r, rt << 1 | 1);
  133.         }
  134.         return ans;
  135.     }
  136. }
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class SegmentTree
  5. {
  6. public:
  7.     int MAXN;
  8.     int *arr;
  9.     int *sum;
  10.     int *lazy;
  11.     int *change;
  12.     bool *update;
  13.  
  14.     SegmentTree(int *origin, int n)
  15.     {
  16.         int MAXN = n + 1;
  17.         this->arr = new int[MAXN];
  18.         for (int i = 1; i < MAXN; i++)
  19.         {
  20.             this->arr[i] = origin[i - 1];
  21.         }
  22.  
  23.         this->sum = new int[MAXN];
  24.         this->lazy = new int[MAXN];
  25.         this->change = new int[MAXN];
  26.         this->update = new bool[MAXN];
  27.  
  28.         for (int i = 0; i < MAXN; i++)
  29.         {
  30.             this->sum[i] = 0;
  31.             this->lazy[i] = 0;
  32.             this->change[i] = 0;
  33.             this->update[i] = false;
  34.         }
  35.     }
  36.  
  37.     // 初始化
  38.     void build(int l, int r, int rt)
  39.     {
  40.         if (l >= r)
  41.         {
  42.             this->sum[rt] = this->arr[l];
  43.             return;
  44.         }
  45.  
  46.         int mid = (l + r) >> 1;
  47.         build(l, mid, rt << 1);
  48.         build(mid + 1, r, rt << 1 | 1);
  49.  
  50.         pushUp(rt);
  51.     }
  52.  
  53.     // add
  54.     void add_f(
  55.         int L, int R, int C,
  56.         int l, int r,
  57.         int rt)
  58.     {
  59.         if (L <= l && R >= r)
  60.         {
  61.             this->sum[rt] += (r - l + 1) * C;
  62.             this->lazy[rt] += C;
  63.             return;
  64.         }
  65.  
  66.         int mid = (l + r) >> 1;
  67.         pushDown(rt, mid - l + 1, r - mid); // 下发任务
  68.  
  69.         if (L <= mid)
  70.         {
  71.             add_f(L, R, C, l, mid, rt << 1);
  72.         }
  73.         if (R > mid)
  74.         {
  75.             add_f(L, R, C, mid + 1, r, rt << 1 | 1);
  76.         }
  77.  
  78.         pushUp(rt);
  79.     }
  80.  
  81.     // update
  82.     void update_f(
  83.         int L, int R, int C,
  84.         int l, int r,
  85.         int rt)
  86.     {
  87.         if (L <= l && R >= r)
  88.         {
  89.             this->update[rt] = true;
  90.             this->change[rt] = C;
  91.             this->sum[rt] = C * (r - l + 1);
  92.             this->change[rt] = 0;
  93.             return;
  94.         }
  95.  
  96.         int mid = (l + r) >> 1;
  97.         pushDown(rt, mid - l + 1, r - mid);
  98.         if (L <= mid)
  99.         {
  100.             update_f(L, R, C, l, mid, rt << 1);
  101.         }
  102.         if (R > mid)
  103.         {
  104.             update_f(L, R, C, mid + 1, r, rt << 1 | 1);
  105.         }
  106.     }
  107.  
  108.     // query
  109.     long query(
  110.         int L, int R, int C,
  111.         int l, int r,
  112.         int rt)
  113.     {
  114.         if (L <= l && R >= r)
  115.         {
  116.             return this->sum[rt];
  117.         }
  118.  
  119.         int mid = (l + r) >> 1;
  120.         pushDown(rt, mid - l + 1, r - mid);
  121.  
  122.         long ans = 0;
  123.         if (L <= mid)
  124.         {
  125.             ans += query(L, R, C, l, mid, rt << 1);
  126.         }
  127.         if (R > mid)
  128.         {
  129.             ans += query(L, R, C, mid + 1, r, rt << 1 | 1);
  130.         }
  131.  
  132.         // pushUp(rt);
  133.         return ans;
  134.     }
  135.  
  136.     void pushDown(int rt, int ln, int rn)
  137.     {
  138.         if (this->update[rt])
  139.         {
  140.             this->update[rt << 1] = true;
  141.             this->update[rt << 1 | 1] = true;
  142.  
  143.             this->change[rt << 1] = this->change[rt];
  144.             this->change[rt << 1 | 1] = this->change[rt];
  145.  
  146.             this->sum[rt << 1] = ln * this->change[rt];
  147.             this->sum[rt << 1 | 1] = rn * this->change[rt];
  148.  
  149.             this->lazy[rt << 1] = 0;
  150.             this->lazy[rt << 1 | 1] = 0;
  151.  
  152.             this->update[rt] = false;
  153.         }
  154.         if (this->lazy[rt] != 0)
  155.         {
  156.             this->lazy[rt << 1] += this->lazy[rt];
  157.             this->sum[rt << 1] += this->lazy[rt] * ln;
  158.             this->lazy[rt << 1 | 1] += this->lazy[rt];
  159.             this->sum[rt << 1 | 1] += this->lazy[rt] * rn;
  160.         }
  161.     }
  162.  
  163.     void pushUp(int rt)
  164.     {
  165.         this->sum[rt] = this->sum[rt << 1] + this->sum[rt << 1 | 1];
  166.     }
  167. };
  168.  
  169. int main()
  170. {
  171.     return 0;
  172. }

六、树状数组

在学习之前千万不要忘记何时使用树状数组

用于处理 单点增减操作，期间多次查询 操作的情况，不如线段树强，但非常容易改造为一维、二维、三维的结构

具体思想：

1. tree数组i位置管理origin数组的部分和

如：

tree[1] = origin[1]

tree[2] = orgin[1]+origin[2]

tree[3] = origin[3]

tree[4] = origin[1]+origin[2]+orgin[3]+origin[4]

tree[5] = origin[5]

...

tree[8] = origin[1]+...+orgin[8]

....

具体算法：

tree[index]管理origin[index二进制表示减最后一个1再加1--index二进制]

如：

Index = 6 => 0110，因此管理origin[0101]到origin[0110]位置的数和

2. 现求origin的index位置到1位置的数和（也就是index位置的前缀和）

（1）index求出二进制xxxxxxx

（2）每次取tree[xxxxxxx]

（3）xxxxxxx减去最后一个1，循环2、3步骤

证明：现求7位置的前缀和

7= 0111,tree的0111位置管理origin的0111-0111的数=>tree[0111]

减去最后一个1=>0110，tree的0110位置管理origin的0101-0110的数=>tree[0110]

减去最后一个1=>0100，tree的0100位置管理origin的0001-0100的数=>tree[0100]

tree[0111]+tree[0110]+tree[0100]=>前缀和，得证

3. 若现在对origin的index位置加d，那么会影响tree的哪些位置

（1）index求出二进制xxxxxxx

（2）tree[xxxxxxx]+d

（3）xxxxxxx加上最后一个1，循环2、3步骤

一维：

  1. public static class IndexTree {
  2.     private int N;
  3.     private int[] tree;
  4.  
  5.     public IndexTree(int size,int[] origin) {
  6.         this.N = size;
  7.         this.tree = new int[N + 1];//树状数组下标从1开始
  8.     }
  9.  
  10.     //每次去掉最后一个一
  11.     public int sum(int index) {
  12.         int ret = 0;
  13.         while (index > 0) {
  14.             ret += tree[index];
  15.             index -= (index) & (-index);
  16.         }
  17.         return ret;
  18.     }
  19.  
  20.     //每次加上最后一个一
  21.     public void add(int index, int d) {
  22.         while (index <= N) {
  23.             this.tree[index] += d;
  24.             index += index & (-index);
  25.         }
  26.     }
  27. }
  1. class IndexTree
  2. {
  3. public:
  4.     int N;
  5.     int *tree;
  6.  
  7.     IndexTree(int size, int *origin)
  8.     {
  9.         this->N = size;
  10.         this->tree = new int[N + 1];
  11.     }
  12.  
  13.     // sum
  14.     int sum(int index)
  15.     {
  16.         int ans = 0;
  17.         while (index > 0)
  18.         {
  19.             ans += tree[index];
  20.             index -= (index) & (-index);
  21.         }
  22.         return ans;
  23.     }
  24.  
  25.     void add(int index, int d)
  26.     {
  27.         while (index <= N)
  28.         {
  29.             tree[index] += d;
  30.             index += index & (-index);
  31.         }
  32.     }
  33. };

二维：

  1. public static class IndexTree2D {
  2.     int N;
  3.     int M;
  4.     int[][] tree;
  5.     int[][] nums;
  6.  
  7.     IndexTree2D(int[][] matrix) {
  8.         N = matrix.length;
  9.         M = matrix[0].length;
  10.         tree = new int[N + 1][M + 1];
  11.         nums = new int[N][M];
  12.  
  13.         for (int i = 0; i < N; i++) {
  14.             for (int j = 0; j < M; j++) {
  15.                 update(i, j, matrix[i][j]);
  16.             }
  17.         }
  18.     }
  19.  
  20.     private int sum(int row, int col) {
  21.         int sum = 0;
  22.         for (int i = row + 1; i > 0; i -= i & -i) {
  23.             for (int j = col + 1; j > 0; j -= j & -j) {
  24.                 sum += tree[i][j];
  25.             }
  26.         }
  27.         return sum;
  28.     }
  29.  
  30.     public void update(int row, int col, int val) {
  31.         if (N == 0 || M == 0) {
  32.             return;
  33.         }
  34.         int add = val - nums[row][col];
  35.         nums[row][col] = val;
  36.  
  37.         for (int i = row + 1; i <= N; i += i & -i) {
  38.             for (int j = col + 1; j <= M; j += j & -j) {
  39.                 tree[i][j] += add;
  40.             }
  41.         }
  42.     }
  43.  
  44.     //从(row1,col1)->(row2,col2)
  45.     int queryRange(int row1, int col1, int row2, int col2) {
  46.         return sum(row2, col2) - sum(row1 - 1, col2) - sum(row2, col1 - 1) + sum(row1 - 1, col1 - 1);
  47.     }
  48. }

  1. class IndexTree2D
  2. {
  3. public:
  4.     int N;
  5.     int M;
  6.     int **tree;
  7.     int **nums;
  8.  
  9.     IndexTree2D(int **matrix, int N, int M)
  10.     {
  11.         this->N = N;
  12.         this->M = M;
  13.         this->tree = new int *[N + 1];
  14.         this->nums = new int *[N];
  15.  
  16.         for (int i = 0; i < N; i++)
  17.         {
  18.             this->tree[i + 1] = new int[M + 1];
  19.             this->nums[i] = new int[M];
  20.         }
  21.  
  22.         for (int i = 0; i < N; i++)
  23.         {
  24.             for (int j = 0; j < M; j++)
  25.             {
  26.                 this->tree[i + 1][j + 1] = 0;
  27.                 this->nums[i][j] = 0;
  28.             }
  29.         }
  30.  
  31.         for (int i = 0; i < N; i++)
  32.         {
  33.             for (int j = 0; j < M; j++)
  34.             {
  35.                 update(i, j, matrix[i][j]);
  36.             }
  37.         }
  38.     }
  39.  
  40.     void update(int row, int col, int val)
  41.     {
  42.         if (N == 0 || M == 0)
  43.             return;
  44.  
  45.         int add = val - nums[row][col];
  46.         nums[row][col] = val;
  47.  
  48.         for (int i = row + 1; i <= N; i += i & -i)
  49.         {
  50.             for (int j = col + 1; j <= M; j += j & -j)
  51.             {
  52.                 tree[i][j] += add;
  53.             }
  54.         }
  55.     }
  56.  
  57.     int sum(int row, int col)
  58.     {
  59.         int ans = 0;
  60.         for (int i = row + 1; i > 0; i -= i & -i)
  61.         {
  62.             for (int j = col + 1; j > 0; j -= j & -j)
  63.             {
  64.                 ans += tree[i][j];
  65.             }
  66.         }
  67.         return ans;
  68.     }
  69. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/654283
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号