前缀和算法详解：高效解决区间求和问题

注意：这里 dp[0] 默认为 0，正好对应区间 [1, 1] 减去空集的情况，逻辑非常自洽。

二维前缀和扩展

对于矩阵区域求和问题，思路与一维类似，但需要处理行和列两个维度。

状态定义与转移

设 dp[i][j] 表示从 (1, 1) 到 (i, j) 矩形区域内所有元素的和。根据容斥原理，当前格子的值等于上方、左方区域之和，减去重复计算的左上角区域，再加上当前格子的值：

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]

区域查询

查询以 (x1, y1) 为左上角，(x2, y2) 为右下角的矩形和时，同样利用容斥原理：

Sum = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

代码实现如下：

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n = 0, m = 0, q = 0; 
    cin >> n >> m >> q;
    
    // 1. 读入数据
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            cin >> arr[i][j];

    // 2. 处理前缀和矩阵
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i-1][j - 1];

    // 3. 使用前缀和矩阵
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while(q--){ 
        cin >> x1 >> y1 >> x2 >> y2; 
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

经典应用场景

理解了模板后，关键在于如何灵活变形。以下是几个高频考点。

寻找数组的中心下标 (LeetCode 724)

题目要求找到一个索引，使得其左侧元素之和等于右侧元素之和。我们可以分别构建前缀和数组和后缀和数组，或者更巧妙地，只维护一个总和，遍历时动态计算左侧和。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        
        int leftSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 右侧和 = 总和 - 左侧和 - 当前元素
            if (leftSum == total - leftSum - nums[i]) 
                return i;
            leftSum += nums[i];
        }
        return -1;
    }
};

除自身以外数组的乘积 (LeetCode 238)

这道题是前缀积的应用。为了避免除法，我们分别计算每个位置左侧的乘积和右侧的乘积，然后相乘。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[n - 1] = 1;
        
        // 计算前缀积
        for(int i = 1; i < n; i++) 
            f[i] = f[i - 1] * nums[i - 1];
        
        // 计算后缀积
        for(int i = n - 2; i >= 0; i--) 
            g[i] = g[i + 1] * nums[i + 1];
            
        vector<int> ret(n);
        for(int i = 0; i < n; i++) 
            ret[i] = f[i] * g[i];
        return ret;
    }
};

和为 K 的子数组 (LeetCode 560)

暴力枚举子数组起点和终点是 O(n²)。利用前缀和，问题转化为：寻找有多少对 (j, i) 满足 prefix[i] - prefix[j] = k，即 prefix[j] = prefix[i] - k。

我们可以用哈希表记录每个前缀和出现的次数。遍历过程中，检查 sum - k 是否在表中，累加次数即可。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int sum = 0, ret = 0;
        hash[0] = 1; // 初始化，处理从开头开始的子数组
        
        for(auto x : nums){
            sum += x;
            if(hash.count(sum - k)) 
                ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

和可被 K 整除的子数组 (LeetCode 974)

基于同余定理，若 (a - b) % k == 0，则 a % k == b % k。因此只需统计相同余数的前缀和数量。

注意：C++ 中负数取模可能为负，需修正为 (sum % k + k) % k。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0 % k]++; // 初始余数为 0
        int sum = 0, ret = 0;
        
        for(auto x : nums){
            sum += x;
            int r = (sum % k + k) % k; // 处理负数取模
            if(hash.count(r)) 
                ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

连续数组 (LeetCode 525)

将 0 视为 -1，1 视为 1。问题转化为寻找和为 0 的最长子数组。此时哈希表存储的是 <前缀和，最早出现下标>，用于计算最大长度。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1; // 默认前缀和为 0 的下标是 -1
        int sum = 0, ret = 0;
        
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i] == 0 ? -1 : 1;
            if(hash.count(sum)) 
                ret = max(ret, i - hash[sum]);
            else 
                hash[sum] = i;
        }
        return ret;
    }
};

矩阵区域和 (LeetCode 1314)

这是二维前缀和的直接应用，但增加了边界限制 k。需要计算以 (i, j) 为中心，边长为 2k+1 的区域和。注意坐标映射和边界裁剪。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        
        // 填充 dp 表
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i - 1][j - 1];
        
        vector<vector<int>> answer(m, vector<int>(n));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                // 计算查询范围，注意边界保护
                int x1 = max(i - k, 0) + 1;
                int y1 = max(j - k, 0) + 1;
                int x2 = min(i + k, m - 1) + 1;
                int y2 = min(j + k, n - 1) + 1;
                
                answer[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
            }
        return answer;
    }
};

前缀和看似简单，但其变体众多。掌握核心递推关系和容斥原理，就能应对绝大多数区间统计问题。在实际编写时，务必注意数组越界和整数溢出风险。