前缀和与差分互为逆运算。
一维前缀和用来求子数组的和，可以将复杂度由$O(n)$降为$O(1)$。
原数组a、前缀和数组s必须在前部有0边界，即a[0] = 0、s[0] = 0；
a[1...n]、s[1...n]存储数据。
for (int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
a[l...r] = s[r] - s[l-1]
注解：
在原数组a上原地计算前缀和数组：
for (int i = 1; i <= n; i++) a[i] += a[i-1];
二维前缀和用来求子矩阵的和，可以将复杂度由$O(n*m)$降为$O(1)$。
原矩阵a、前缀和矩阵s必须在前部有0边界，即a[0][0...n] = a[0...n][0] = 0、s[0][0...n] = s[0...n][0] = 0；
a[1...n][1...n]、s[1...n][1...n]存储数据。
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
a[x1...x2][y1...y2] = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
注解：
在原矩阵s上原地计算前缀和矩阵：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];