前缀和&差分（注意让下标都从1开始）

一维前缀和（两个公式 1. 前缀和公式 2. 部分和公式）

定义原数组a[],令 s[i] = s[i-1] + a[i], s[0] = 0 , 则称s[]为原数组的前缀和数组
核心操作：以l为左边界，r为右边界的区间和等价于部分和公式 s[r] - s[l-1]
前缀和公式: s[i] = s[i - 1] + a[i]

一维差分 (一个插入公式)

定义原数组a[], 差分数组b[], 令a[]为b[]数组的前缀和数组，则称b[]为a[]的差分数组
核心操作：以l为左边界，r为右边界的区间加上c，可以用O(1)的时间复杂度在差分数组上计算出结果。等价于在差分数组上执行 b[l] += c, b[r+1] -= c

二位前缀和 （两个公式 1. 前缀和公式 2. 部分和公式）

核心操作：以 (x1, y1)为左上角，(x2, y2)为右下角的子矩阵之和，部分和 res = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]
部分和公式： s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

二维差分（一个插入公式）

核心操作：以 (x1, y1)为左上角，(x2, y2)为右下角的子矩阵加上c，等价于 在差分矩阵上执行b[x1][y1] += c, b[x1][y2+1] -= c, b[x2+1][y1] -= c, b[x2][y2] += c