一、前缀和

1.一维前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 i 项的和”。
PS：C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 中。

例题：

有 N 个的正整数放到数组 A 里，现在要求一个新的数组 B，新数组的第 i 个数 B[i] 是原数组 A 第 0 到第 i 个数的和。

  1. 5
  2. 1 2 3 4 5
  1. 1 3 6 10 15

解题思路：
递推：B[0] = A[0]，对于 i≥1 则 B[i] = B[i-1] + A[i]。
前缀和可以以O(1)的时间查询原数组中第 i - j 个数的和，是一种十分高效的处理技巧。

2.二维/多维前缀和

多维前缀和的普通求解方法几乎都是基于容斥原理。

示例：

比如我们有这样一个矩阵 A ，可以视为二维数组：

  1. 1 2 4 3
  2. 5 1 2 4
  3. 6 3 5 9

我们定义一个矩阵 B 使得 ，B[i][j] 等于 ( 0 , 0 )到( i , j )中所有数的和，那么这个矩阵长这样：

  1. 1  3  7  10
  2. 6  9  15 22
  3. 12 18 29 45

我们可以递推求出矩阵B，递推过程为B[m][n] = B[m-1][n] + B[m][n-1] - B[m-1][n-1] + A[m][n]
为何？
前缀和与差分 - 图1
红色 部分元素和 : B[m-1][n-1]

红色 + 黄色 部分元素和：B[m - 1][ n]

红色 + 绿色 部分元素和：B[m][n - 1]

蓝色 部分：新加的元素，以 A[m][n] 表示
很显然，我们在求解B[m-1][n] + B[m][n-1]后，多加了一遍红色区域，所以要减去。

前半部分已经完成，而快速查询子矩阵元素和的步骤应该也可以利用容斥原理推出。
前缀和与差分 - 图2
要求以 (a, b) 为左上角，(c, d) 为右下角的矩形 (蓝色部分) 的元素和。
按照同样的套路，通过拆添项解决问题。

蓝色部分 = 整体部分 - 红色部分 - 黄色部分 - 绿色部分
= 整体部分 - （红色部分 + 黄色部分）- （红色部分 + 绿色部分） + 红色部分
= B[c][d] - B[a - 1][d] - B[c][b - 1] + B[a - 1][b - 1]

二、差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
这种策略的定义是令前缀和与差分 - 图3
它可以O(1)维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

C++ 标准库中实现了差分函数 std::adjacent_difference，定义于头文件 中。