前缀和与差分

一维前缀和

• 开辟一个新的数组（或者直接使用原数组），用来存储i节点前的所有数之和
• 可以以O(1)的时间复杂度获取和或者某个区间内的和

二维前缀和

- 由上图可以得到： s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] - 由该式我们可以得到任意方阵的和

差分

• 前缀和的逆运算