前缀和 & 差分数组

概览

前缀和：用 O(n) 预处理，把区间求和从 O(n) 降到 O(1)。差分数组是前缀和的逆运算：用 O(1) 完成区间加法，O(n) 重建数组。两者都是以「空间换时间」的思路，是处理区间问题的基础工具。

对偶关系

前缀和数组的「差分」就是原数组；差分数组的「前缀和」就是原数组。即 diff[i] = nums[i] − nums[i-1]，prefix[i] = prefix[i-1] + nums[i-1]。理解这个互逆关系，两种结构自然融会贯通。

// Prefix sum  →  diff of prefix = original
prefix[i] = prefix[i-1] + nums[i-1]

// Difference array  →  prefix of diff = original
diff[i] = nums[i] - nums[i-1]

使用场景对比

一维前缀和

预先计算累积和数组 prefix[]，使得任意区间 [l, r] 的和可在 O(1) 内得出。

核心思想

定义 prefix[i] = nums[0] + nums[1] + ... + nums[i-1]（1-indexed，prefix[0] = 0）。则区间 [l, r]（0-indexed）的和为 prefix[r+1] - prefix[l]。用前缀相减抵消了公共前缀，无需重复相加。

步骤

1. 建立 prefix 数组，大小为 n+1，prefix[0] = 0
2. for i in [0, n): prefix[i+1] = prefix[i] + nums[i]
3. 区间查询：sum(l, r) = prefix[r+1] - prefix[l]（0-indexed 闭区间）
4. 多次查询时，只需建一次 prefix，每次查询 O(1)

C++ 实现

// Build prefix sum (1-indexed)
// prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
vector<long long> buildPrefix(vector<int>& nums) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

// Range sum query [l, r] inclusive (0-indexed)
long long rangeSum(vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

常见错误

前缀和 + 哈希表

在遍历时维护当前前缀和，并用哈希表记录每个前缀和出现的次数。可在 O(n) 内统计满足条件的子数组数目。

核心思想

子数组 [i, j] 的和 = prefixSum[j+1] - prefixSum[i]。若要找和等于 k 的子数组，等价于找满足 prefixSum[i] = prefixSum[j+1] - k 的 i。在遍历 j 时，用哈希表存所有已见的 prefixSum[i]，即可 O(1) 查询。

步骤（子数组和等于 k）

1. 初始化哈希表 cnt，令 cnt[0] = 1（空前缀和为 0，计数 1）
2. 维护 prefixSum = 0，ans = 0
3. 遍历每个 nums[j]：prefixSum += nums[j]
4. ans += cnt[prefixSum - k]（查找已有的配对前缀）
5. cnt[prefixSum]++（记录当前前缀和）
6. 返回 ans

C++ 实现

// Count subarrays with sum exactly equal to k
int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> cnt;
    cnt[0] = 1;           // empty prefix has sum 0
    long long prefixSum = 0;
    int ans = 0;
    for (int x : nums) {
        prefixSum += x;
        ans += cnt[prefixSum - k]; // look up existing matching prefix
        cnt[prefixSum]++;          // record current prefix (AFTER lookup!)
    }
    return ans;
}

常见变体

常见错误

二维前缀和

将一维前缀和推广到矩阵，用容斥原理在 O(1) 内查询任意矩形区域的元素之和。

核心思想

定义 p[i][j] = 矩形 [0,0] 到 [i-1,j-1] 的元素和（1-indexed）。建立公式：p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]。查询 [r1,c1] 到 [r2,c2]（0-indexed）：p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]。

// Inclusion-exclusion (2D):
//
//   p[i][j] = ████ (big rect)
//           = grid[i-1][j-1]
//           + p[i-1][j]   (rect above)
//           + p[i][j-1]   (rect to left)
//           - p[i-1][j-1] (overlap counted twice)
//
// Query [r1,c1]..[r2,c2]:
//   p[r2+1][c2+1]        (big rect)
//   - p[r1][c2+1]         (top strip)
//   - p[r2+1][c1]         (left strip)
//   + p[r1][c1]           (corner added back)

步骤

1. 建 (m+1)×(n+1) 的 prefix 数组，所有值初始为 0
2. 二重循环填充：p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
3. 查询矩形 [r1,c1,r2,c2]（0-indexed）：
4. → p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]

C++ 实现

// Build 2D prefix sum (1-indexed)
// p[i][j] = sum of rectangle grid[0..i-1][0..j-1]
vector<vector<long long>> build2D(vector<vector<int>>& g) {
    int m = g.size(), n = g[0].size();
    vector<vector<long long>> p(m+1, vector<long long>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            p[i][j] = g[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
    return p;
}

// Query sum of rectangle [r1,c1]..[r2,c2] (0-indexed, inclusive)
long long query2D(vector<vector<long long>>& p, int r1, int c1, int r2, int c2) {
    return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];
}

常见错误

差分数组

对原数组做「差分」得到 diff[]，每次区间 [l, r] 加 val 只需 O(1)：diff[l]+=val, diff[r+1]-=val。全部更新完毕后，对 diff 求前缀和即可重建原数组。

核心思想

diff[i] = nums[i] - nums[i-1]（diff[0] = nums[0]）。对 [l, r] 加 val：让 diff[l]+=val（l 处开始生效）、diff[r+1]-=val（r+1 处抵消）。最终对 diff 求一次前缀和还原出修改后的 nums。适合「离线批量区间更新，最后统一输出」的场景。

// Range add val to [l, r]:
//
//  diff: [0  0  0  0  0]
//              +val      -val
//  after add [1,3] val=2:
//  diff: [0  2  0  0 -2]
//
//  prefix sum → nums: [0  2  2  2  0]  ✓

步骤

1. 构建 diff：diff[0]=nums[0]，diff[i]=nums[i]-nums[i-1] (i>=1)
2. 对每次区间更新 (l, r, val)：diff[l]+=val；若 r+1<n 则 diff[r+1]-=val
3. 所有更新完成后，对 diff 求前缀和重建 nums：nums[i]=nums[i-1]+diff[i]
4. 输出最终数组

C++ 实现

// Build difference array
// diff[i] = nums[i] - nums[i-1]  (diff[0] = nums[0])
vector<int> buildDiff(vector<int>& nums) {
    int n = nums.size();
    vector<int> diff(n);
    diff[0] = nums[0];
    for (int i = 1; i < n; i++) diff[i] = nums[i] - nums[i-1];
    return diff;
}

// Range add val to [l, r] (0-indexed, inclusive) — O(1)
void rangeAdd(vector<int>& diff, int l, int r, int val) {
    diff[l] += val;
    if (r + 1 < (int)diff.size()) diff[r + 1] -= val;
}

// Rebuild original array by prefix-summing diff — O(n)
vector<int> rebuild(vector<int>& diff) {
    int n = diff.size();
    vector<int> nums(n);
    nums[0] = diff[0];
    for (int i = 1; i < n; i++) nums[i] = nums[i-1] + diff[i];
    return nums;
}

差分数组 vs 线段树

常见错误

LeetCode 题型

按技术分类的高频前缀和题目。

一维前缀和

前缀和 + 哈希表

二维前缀和

差分数组