前缀和
用于快速求出一个静态数组某一个区间内所有数的和，可以有效提高算法运行效率
与树状数组和线段树的比较
- 优点：时间复杂度低
- 缺点：不能随时修改数据
AcWing 795. 前缀和
一维前缀和
- 两个数组：s[N],a[N]
- s[i] = a[1] + a[2] + ... + a[i] ，等价于 s[i] = s[i - 1] + a[i]
- 求 a[l] + ... + a[r] : s[r] - s[l - 1] ,查询的时间复杂度为 $O(1)$
代码
AcWing 796. 子矩阵的和
二维前缀和
- 两个二维数组 s[N][N],a[N][N]
- s[i][j] 表示 (i,j) 左上角所有数（包含 (i,j))的和，即 s[i][j]=a[1][1]+a[1][2]+...+a[1][j]+...+a[i][j]
- 通过容斥原理可以得出，s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]
- 求 (x1,y1) 和 (x2,y2) 之间所有数的和：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
