前缀和与差分
两个内容都比较少，就放一起写了
设数组 a 的前 n 项为a1 , a2 , a3 ... an
前缀和数组就是每一项是a数组的前i项和，比如前缀和数组res，res[ 1 ] = a[ 1 ]，res[ 2 ] = a[ 1 ] + a [ 2 ]，res[ n ] = a[ 1 ] + a [ 2 ] + ... + a[ n ]
前缀和可以在O(1)的时间内计算一段区间内的累加和，比如区间 l ~ r 之间的元素累加和为res[ r ] - res [ l - 1]
一维前缀和：
res[ i ] = a[ 1 ] + a[ 2 ] + ... a[ i ]
二维前缀和：
res[ i, j ] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为 res[x2, y2] - res[x1 - 1, y2] - res[x2, y1 - 1] + res[x1 - 1, y1 - 1]
给定数组res，用前缀和数组 res 求出来的 a 数组就是差分数组，差分和前缀和互为逆运算
一维差分：
B[i] = a[i] - a[i - 1]
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
二维差分：
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c