一维前缀和

公式

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

注意事项

• 下标需要从1开始，初始化S~0~=0
• S[i]=S[i-1]+a[i]

应用

用来计算闭区间[l,r]之间的元素和：a[l] + … + a[r] = S[r] - S[l - 1]

二维前缀和

公式

S[i, j] = 第i行j列格子左上部分所有元素的和

以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

因为包含点（i，j）的值，所以要有“-1”

注意事项：

• S[i][j]的存储行列下标都从1开始