前缀和 & 差分
前缀和
定义
前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。1
C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 中。
二维/多维前缀和
多维前缀和的普通求解方法几乎都是基于容斥原理。
示例：一维前缀和扩展到二维前缀和
比如我们有这样一个矩阵 a，可以视为二维数组：
我们定义一个矩阵 \textit{sum} 使得
\textit{sum}{x,y} = \sum\limits{i=1}^x \sum\limits_{j=1}^y a_{i,j}，
那么这个矩阵长这样：
1 3 7 10
6 9 15 22
12 18 29 45
第一个问题就是递推求 \textit{sum} 的过程，\textit{sum}{i,j} = \textit{sum}{i - 1,j} + \textit{sum}{i,j - 1} - \textit{sum}{i - 1,j - 1} + a_{i,j}。
因为同时加了 \textit{sum}{i - 1,j} 和 \textit{sum}{i,j - 1}，故重复了 \textit{sum}_{i - 1,j - 1}，减去。
第二个问题就是如何应用，譬如求 (x_1,y_1) - (x_2,y_2) 子矩阵的和。
那么，根据类似的思考过程，易得答案为 \textit{sum}{x_2,y_2} - \textit{sum}{x_1 - 1,y_2} - sum_{x_2,y_1 - 1} + sum_{x_1 - 1,y_1 - 1}。
例题
洛谷 P1387 最大正方形
在一个 n\times m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形，输出边长。
参考代码
基于 DP 计算高维前缀和
基于容斥原理来计算高维前缀和的方法，其优点在于形式较为简单，无需特别记忆，但当维数升高时，其复杂度较高。这里介绍一种基于 DP 计算高维前缀和的方法。该方法即通常语境中所称的 高维前缀和。
设高维空间 U 共有 D 维，需要对 f[\cdot] 求高维前缀和 \text{sum}[\cdot]。令 \text{sum}[i][\text{state}] 表示同 \text{state} 后 D - i 维相同的所有点对于 \text{state} 点高维前缀和的贡献。由定义可知 \text{sum}[0][\text{state}] = f[\text{state}]，以及 \text{sum}[\text{state}] = \text{sum}[D][\text{state}]。
其递推关系为 \text{sum}[i][\text{state}] = \text{sum}[i - 1][\text{state}] + \text{sum}[i][\text{state}‘]，其中 \text{state}’ 为第 i 维恰好比 \text{state} 少 1 的点。该方法的复杂度为 O(D \times |U|)，其中 |U| 为高维空间 U 的大小。
一种实现的伪代码如下：
树上前缀和
设 \textit{sum}_i 表示结点 i 到根节点的权值总和。
然后：
若是点权，x,y 路径上的和为 \textit{sum}x + \textit{sum}y - \textit{sum}\textit{lca} - \textit{sum}{\textit{fa}_\textit{lca}}。
若是边权，x,y 路径上的和为 \textit{sum}_x + \textit{sum}y - 2\cdot\textit{sum}{lca}。
LCA 的求法参见 最近公共祖先。
差分
解释
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
这种策略的定义是令
b_i=\begin{cases}a_i-a_{i-1},&i \in[2,n] \ a_1,&i=1\end{cases}
性质
a_i 的值是 b_i 的前缀和，即
a_n=\sum\limits_{i=1}^nb_i
计算 a_i 的前缀和
sum=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}b_j=\sum\limits_{i}^n(n-i+1)b_i
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
示例
譬如使 [l,r] 中的每个数加上一个 k，即
b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k
其中 b_l+k=a_l+k-a_{l-1}，b_{r+1}-k=a_{r+1}-(a_r+k)
最后做一遍前缀和就好了。
C++ 标准库中实现了差分函数 std::adjacent_difference，定义于头文件 中。
树上差分
树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。
树上差分通常会结合 树基础 和 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分，在实现上会稍有不同。
点差分
举例：对树上的一些路径 \delta(s_1,t_1), \delta(s_2,t_2), \delta(s_3,t_3)\dots 进行访问，问一条路径 \delta(s,t) 上的点被访问的次数。
对于一次 \delta(s,t) 的访问，需要找到 s 与 t 的公共祖先，然后对这条路径上的点进行访问（点的权值加一），若采用 DFS 算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作：
其中 f(x) 表示 x 的父亲节点，d_i 为点权 a_i 的差分数组。
可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令 \textit{lca} 左侧的直系子节点为 \textit{left}。那么有 d_{\textit{lca}}-1=a_{\textit{lca}}-(a_{\textit{left}}+1)，d_{f(\textit{lca})}-1=a_{f(\textit{lca})}-(a_{\textit{lca}}+1)。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。
边差分
若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式：
由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值向下移动到附近的点里，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。