前缀和

一维前缀和

S[0] = 0
S[i] = a[0] + a[1] + a[2] + ... + a[i - 1]
S[i + 1] = S[i] + a[i]
a[l] + ... + a[r] = S[r + 1] - S[l]

//原地前缀和
for (int i = 1; i < length; i++) {
    nums[i] += nums[i - 1];
}

二维前缀和

S[i, j] = 二维数组a[i,j]第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]

差分

一维差分

给区间[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