由于王某某的强烈谴责，临时决定删除对其的檄文一日，望周知

I 前缀和与差分

一维前缀和：

前缀和是用于计算区间和的快捷方式，其时间复杂度为O(1)

设原数组为num, 前缀和数组为sum, 则在定义sum时存在：

$sum_i = sum_{i-1} + num_i (i \geqslant 1)$

那么，求num数组[i,j]之间数据的和可以表达为

$sum_j - sum_{i-1}$

一维差分：

差分可以理解为前缀和的逆运算，其用来区间加同一个数

同样的，设原数组为num, 则将num数组[i,j]之间的数同一加x可以：

$num_i + x, num_{j+1} -x$

然后将num进行前缀和计算

二维前缀和

设原数组为num, 前缀和数组为sum, 那么sum[i][j]则表示区间0,0到i,j内所有元素的和

举个例子

有个二维数组num，如下：

1	2	3	4
5	6	7	8
9	10	11	12

那么二维前缀和sum[i][j]可以表达为：

s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + num[i][j];

这是图解 （红色等于黄色加蓝色减重复的绿色）

二维差分

同差分，二维差分是用来矩阵统一加减

不多BB，直接给出：

设原数组为num,差分数组diff（最开始同num一致）则我们可以这样做：

diff[x1][y1] += c; diff[x1][y2+1] -=c; diff[x2+1][y1] -=c; diff[x2+1][y2+1] += c;

最后在对diff求前缀和即可

II 树

// 未完待续……