前缀和.md

总纲

前缀和的基础思路是，对于给定的数组，另外开辟一个前缀和数组进行处理。一般用于处理数组区间问题。

int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
    preSum[i + 1] = preSum[i] + nums[i];
    
// 二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
S[i,j] = S[i,j−1] + S[i−1,j] − S[i−1,j−1] + a[i,j]
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和
sum = S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

preSum[i] 相当于 nums[0...i-1]的和，preSum[j+1] - preSum[i] 相当于 nums[i...j]的和。

前缀和能和差分、单调栈一起考察，有时也需要备忘录减少时间复杂度。

题目举例

题号	题目	难度
303	区域和检索-数组不可变	简单
304	二维区域和检索-矩阵不可变	中等
560	和为k的子数组	中等
1124	表现良好的最长时间段	中等