当需要多次计算给定连续区间内的数之和时，如果暴力算法它的时间复杂度较高，有没有能在查询阶段是常数量级的方法呢？当需要多次将给定连续区间上的数都加上一个常数C时，有没有什么快速的方法，将较高的时间复杂度降低呢？
…

前缀和与差分

设原数组为A，其中的第i个元素为$a_i$，则前缀和数组的第i个位置的元素$S_i = a_1 + a_2 + ... + a_i$，即：前缀和数组中的第i个元素等于原数组中前i个（下标从1开始）的和。

这里需要注意的是：对于前缀和数组来说，下标一定要从1开始而不是从0开始。

有两个问题：

1. 如何求前缀和数组中的第i个元素$S_i$？
2. 前缀和数组中的元素$S_i$是用来做什么用的？有什么作用？

前缀和

一维数组的前缀和

求元素$S_i$

将边界值$S_0$设为0，则可以使用迭代公式：$S_i = S_{i-1} + a_i$即可计算出来，其代码为：

for (int i = 1; i <= n; ++i) {
  S[i] = S[i - 1] + A[i];
}

需要注意的是，如果使用上述公式来求元素$S_i$的话，那么在输入阶段，原始数组的下标也要从0挪到从1开始。

前缀和中的第0个元素为什么要设计成值为0，并且前缀和数组的下标是从1开始的？原因是为了统一操作，将求原数组中某一区间内的元素和的公式统一，不用处理边界值，不用再进行条件判断而设置的哨兵节点。

前缀和的作用

可以快速的求出原数组中一段元素的和，如：求[l, r]范围内的元素的和，其值为：$S_r - S_{l - 1}$。

为什么值是上述公式呢？不要忘记前缀和数组中的元素的定义。它的定义原数组中，前i个元素的和。

二维数组的前缀和

求元素$S_i$

对于二维数组的前缀和元素$S_{ij}$表示的是：$S_{ij}$左上角部分的那一块子矩阵的元素的和。

如下图所示：

橘黄色部分的元素之和等于绿颜色矩形中的元素之和加上蓝颜色举行中的颜色之和减去重复运算的蓝绿矩形的交集中的元素之和，最后加上元素$a_{ij}$，即：$S_{ij} = S_{i - 1, j} + S_{i, j - 1} - S_{i -1, j- 1} + a_{ij}$

for (int i = 1; i <= m; ++i) {
  for (int j = 1; j <= n; ++j) {
    S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
  }
}

在记忆的时候，可以按照上述颜色的图形来记忆，也可以找参照物，即：使用子矩阵的右下角坐标为参照物，找上述颜色中的矩形是和它是同一行、前一行、同一列还是前一列。这样就可以快速写出上述公式了。

求给定区间范围内的元素之和

其实就是利用的集合的操作，给定两个坐标点$(x_1, y_1)$和$(x_2, y_2)$，则在这两个点内的矩阵的元素之和为：

$$S_{x_2, y_2} - S_{x_1 - 1, y_2} - S_{x_2, y_1 - 1} + S_{x_1 - 1, y_1 - 1}$$

其中：

• $S_{x_1 - 1, y_2}$代表的是左侧部分的长方形矩阵
• $S_{x_2, y_1 - 1}$代表的是上面部分的长方形矩阵
• $S_{x_1 - 1, y_1 - 1}$代表的是被重复减去的那一块正方形矩阵

快速写出上述求解公式的方法与求元素$S_i$一致，以待求子矩阵的左上角坐标和右下角坐标为参照物，找到参与运算的子矩阵元素是和这些坐标是同一行、同一列、前一行还是前一列即可快速写出。

差分

差分和前缀和是一组逆运算。设原数组A中的第i个元素为$a_i$，需要构造一个数组B，使得数组A是数组B的前缀和数组，即：$a_i = b_1 + b_2 + ... + b_i$。B数组称为数组A的差分数组，A数组称为B数组的前缀和数组。

一维数组

差分数组的构造与更新

对于一维数组的差分是比较好构造的，设：

$$b_1 = a_1 \\ b_2 = a_2 - a_1 \\ ... \\ b_i = a_i - a_{i - 1}$$

从而有：$a_i = b_1 + b_2 + ... + b_i$

假设原来的数组A中的元素都是0（不管实际中给定的数组A中的元素是否是0，我们都假设原来数组A中的元素都是0），则差分数组B中的元素应该都是0（因为这样才能满足差分数组的定义），这样自然而然的就不需要对差分数组进行初始化了。

将给定的数组A中的每一个元素视为要加的常数C，那么就可以定义一个插入操作：

void insert(int l, int r, int C) {
  B[l] += C;
  B[r + 1] -= C;
}

则对应数组A的差分数组为：insert(i, i, A[i])，$i \in [1, n]$。转为代码为：

for (int i = 1; i <= n; ++i) {
  insert(i, i, A[i]);
}

利用哨兵数组（假定原数组中的所有元素均为0，则差分数组中的元素均为0），将差分数组的初始化和对给定连续区间[l, r]内的原数组中的元素都加上常数C的操作统一起来，不用再做额外的操作。

即：利用哨兵技巧，不用考虑差分数组的构造而只需要将精力放到如何更新差分数组中的元素即可。

差分数组的应用

差分数组的性质是：只需要对B数组求一遍前缀和，就可以得到原数组。

如果对于原数组A中指定的连续区间[l, r]中的每一个元素都需要加上一个常数C，而保持[r + 1, n]上的元素不变，直接对原数组A进行操作的话需要的时间复杂度是O(n)的，而如果使用差分数组则可以将上述操作的时间复杂度降低为O(1)。

如何操作呢？只需要将元素$b_l$加上一个常量C和$b_{r + 1}$上的元素减去一个C即可。根据差分数组的性质，如果只有一个$b_l + C$，则在求原数组中的元素时，区间[l, n]上的所有元素都会加上C。只需要保证[r + 1, n]上的元素不变即可，那么只需要$b_{r +1} -C$即可保证[r + 1, n]上的元素不变。这就相当于是把连续区间[l, r]上的原数组中的所有元素都加上了一个常数C

二维数组

一维数组是将给定的连续区间范围的原数组中的元素均加上一个常数C；而二维数组的操作是对于给定的子矩阵中的每一个元素均加上一个常数C

差分数组的构造与更新

根据一维差分数组的性质与更新方式，对于二维数组的差分数组也是一样的，对起始点加上一个常量C，以该点为起始点的右下角矩阵中的所有元素都加上常量C。所以，二维数组中的差分数组为了保证还是原数组A的差分数组，则需要进行一系列的调整。

根据上图所示，设：$(x, y) = (x_1, y_1),(i, j) = (x_2, y_2)$，则对于原数组A中给定待操作矩阵中每个元素加上常数C，等价于差分数组：

$$B_{x_1, y_1} = B_{x_1, y_1} + C \\ B_{x_1, y_2} = B_{x_1, y_2} - C \\ B_{x_2, y_1} = B_{x_2, y_1} - C \\ B_{x_2 + 1, y_2 + 1} = B_{x_2 + 1, y_2 + 1} + C$$

用代码表示的话则是：

void insert(int x1, int y1, int x2, int y2, int C) {
  B[x1][y1] += C;
  B[x1][y2 + 1] -= C;
  B[x2 + 1][y1] -= C;
  B[x2 + 1][y2 + 1] += C;
}

二维差分数组的构造和一维差分数组的构造一样，利用哨兵，可以将差分数组的构造和更新的操作统一起来。构造二维差分数组的方法为：

insert(i, j, i, j, a[i][j]);

该函数的作用是：起始点坐标到终点坐标的矩阵中的元素都加上常数C。所以在插入原数组时，其实就是在说：在当前坐标下，将原数组的元素a[i][j]视为常数C，使其满足以元素a[i][j]为其前缀和的差分性质。

在最后计算加和得到原矩阵时，使用的是计算前缀数组的方式来迭代计算的。也就是说要根据差分矩阵计算原矩阵，其实就是求前缀和的过程。所以需要使用二维数组求前缀和的方式来计算。