📘 前缀和算法模板（Java）
本文整理了 8 大常见前缀和算法模板，方便直接复用。
1) 一维前缀和（基础）
思路：构造 prefix[i] = nums[0..i-1]，查询区间和 O(1)。
public class PrefixSum1D {
private long[] prefix; // prefix[i] = sum(nums[0..i-1])
public PrefixSum1D(int[] nums) {
int n = nums.length;
prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
// 区间和 nums[l..r]
public long rangeSum(int l, int r) {
if (l > r) return 0;
return prefix[r + 1] - prefix[l];
}
}
- 构造 O(n)，查询 O(1)
2) 前缀和 + 哈希表（统计子数组个数）
思路：哈希表记录前缀和出现次数，统计目标区间数量。
public int subarraySumEqualsK(int[] nums, int k) {
Map<Long, Integer> count = new HashMap<>();
count.put(0L, 1);
long prefix = 0;
int res = 0;
for (int x : nums) {
prefix += x;
res += count.getOrDefault(prefix - k, 0);
count.put(prefix, count.getOrDefault(prefix, 0) + 1);
}
return res;
}
- 经典题：560. Subarray Sum Equals K
- 时间/空间：O(n)
3) 差分数组（前缀和逆运算）
思路：区间更新时用差分，最后统一恢复。
public int[] applyRangeUpdates(int n, int[][] updates) {
// updates: {l, r, val}
long[] diff = new long[n + 1];
for (int[] up : updates) {
int l = up[0], r = up[1], val = up[2];
diff[l] += val;
if (r + 1 < diff.length) diff[r + 1] -= val;
}
int[] result = new int[n];
long cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
result[i] = (int) cur;
}
return result;
}
- 典型题：370, 1094, 1109
- 复杂度：O(n + m)
4) 二维前缀和（矩阵）
思路：pre[i][j] 表示 (0,0) 到 (i-1,j-1) 的和，查询用容斥。
public class PrefixSum2D {
private long[][] pre;
public PrefixSum2D(int[][] mat) {
int m = mat.length, n = (m == 0 ? 0 : mat[0].length);
pre = new long[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
pre[i][j] = mat[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
}
}
}
public long sumRegion(int r1, int c1, int r2, int c2) {
int i1 = r1 + 1, j1 = c1 + 1, i2 = r2 + 1, j2 = c2 + 1;
return pre[i2][j2] - pre[i1-1][j2] - pre[i2][j1-1] + pre[i1-1][j1-1];
}
}
- 典型题：304, 1314
- 构造 O(mn)，查询 O(1)
5) 前缀和 + 滑动窗口 / 双指针
思路：前缀和计算区间和，窗口控制长度（数组需非负）。
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length, left = 0, right = 0;
long sum = 0;
int ans = Integer.MAX_VALUE;
while (right < n) {
sum += nums[right++];
while (sum >= target) {
ans = Math.min(ans, right - left);
sum -= nums[left++];
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
- 典型题：209
- 复杂度：O(n)
6) 前缀和 + 单调队列
思路：维护单调递增前缀和索引，用于最短子数组 ≥ K（含负数）。
public int shortestSubarrayAtLeastK(int[] A, int K) {
int n = A.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i+1] = pre[i] + A[i];
Deque<Integer> dq = new ArrayDeque<>();
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= n; i++) {
while (!dq.isEmpty() && pre[i] - pre[dq.peekFirst()] >= K) {
ans = Math.min(ans, i - dq.pollFirst());
}
while (!dq.isEmpty() && pre[i] <= pre[dq.peekLast()]) {
dq.pollLast();
}
dq.addLast(i);
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
- 典型题：862
- 复杂度：O(n)
7) 前缀和 + 异或（前缀 XOR）
思路：xor[l..r] = pre[r+1] ^ pre[l]
public int[] xorQueries(int[] arr, int[][] queries) {
int n = arr.length;
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i+1] = pre[i] ^ arr[i];
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; i++) {
int l = queries[i][0], r = queries[i][1];
ans[i] = pre[r+1] ^ pre[l];
}
return ans;
}
- 典型题：1310, 1442
- 复杂度：O(n + q)
8) 前缀和 + 前缀最值
Kadane（经典 DP）
public int maxSubArrayKadane(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}
前缀最小值法
public int maxSubArrayPrefix(int[] nums) {
long prefix = 0, minPrefix = 0, best = Long.MIN_VALUE;
for (int x : nums) {
prefix += x;
best = Math.max(best, prefix - minPrefix);
minPrefix = Math.min(minPrefix, prefix);
}
return (int) best;
}
- 典型题：53, 643
- 复杂度：O(n)
✨ 总结口诀
- 区间和 → 前缀数组
- 子数组个数 → 前缀和 + 哈希表
- 区间更新 → 差分
- 矩阵问题 → 二维前缀和
- 区间长度优化 → 滑动窗口 / 单调队列
- 异或问题 → 前缀 XOR
- 子数组最大/最小 → 前缀和 + 前缀最值