前缀和算法详解：从一维到二维的实战应用

2. 二维前缀和

核心思路：

一维的扩展。若我们能计算出从 (0, 0) 到 (i, j) 矩形区域内所有元素的累加和，就能在 O(1) 时间内获取任意子矩阵的和。

为了简化边界判断，通常在原矩阵外围添加一行和一列 0。这样 DP 表的下标直接从 1 开始，无需特殊处理 i=0 或 j=0 的情况。

坐标映射关系：

• DP 表 sum[i][j] 对应原矩阵 matrix[i-1][j-1]。
• sum[i][j] 表示左上角 (0,0) 到右下角 (i,j) 的红色区域和。

递推方程： 观察图形分解，sum[i][j] 可以看作： sum[i-1][j] (上方矩形) + sum[i][j-1] (左方矩形) - sum[i-1][j-1] (重叠部分) + matrix[i-1][j-1] (当前元素)

即：

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]

查询操作： 给定左上角 (row1, col1) 和右下角 (row2, col2)，对应的 DP 表下标需相应调整。利用容斥原理：

Result = sum[row2][col2] 
         - sum[row2][col1-1] 
         - sum[row1-1][col2] 
         + sum[row1-1][col1-1]

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

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    
    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];
        }
    }

    // 初始化二维前缀和数组
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    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] - dp[i - 1][j - 1] + arr[i][j];
        }
    }

    int x1, y1, x2, y2;
    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;
}

3. 寻找数组的中心下标

思路： 中心下标左侧元素之和等于右侧元素之和。我们可以分别预处理前缀和与后缀和数组，然后遍历查找相等的位置。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);
        
        // 前缀和
        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];
        }
        
        for (int i = 0; i < n; i++) {
            if (g[i] == f[i]) return i;
        }
        return -1;
    }
};

4. 除自身以外数组的乘积

思路： 题目限制不能使用除法且要求 O(N) 时间。对于每个位置 i，结果由两部分组成：i 左侧所有数的乘积 × i 右侧所有数的乘积。

利用类似前缀和的思想，用两个数组分别记录前缀乘积和后缀乘积。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1), ans(n);
        
        // 前缀乘积
        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];
        }
        
        for (int i = 0; i < n; i++) {
            ans[i] = f[i] * g[i];
        }
        return ans;
    }
};

5. 和为 K 的子数组

思路： 设 sum[i] 为 [0, i] 的前缀和。若存在起始位置 x 使得 [x, i] 的和为 k，则 sum[i] - sum[x-1] = k，即 sum[x-1] = sum[i] - k。

问题转化为：在当前位置之前，有多少个前缀和等于 sum[i] - k？使用哈希表统计前缀和出现的次数即可。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 初始前缀和为 0
        int sum = 0, ret = 0;
        
        for (auto x : nums) {
            sum += x;
            if (hash.count(sum - k)) {
                ret += hash[sum - k];
            }
            hash[sum]++;
        }
        return ret;
    }
};

6. 和可被 K 整除的子数组

前置知识： 同余定理：若 (a - b) % n == 0，则 a % n == b % n。

C++ 取模陷阱： C++ 中负数取模结果为负（如 -1 % 3 = -1）。为保证余数为正，统一使用 (a % n + n) % n。

思路： 与上一题类似，只需判断前缀和的余数是否相同。若 sum[i] % k == sum[x-1] % k，则中间段可被 k 整除。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 余数为 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;
    }
};

7. 连续数组

思路： 将 0 视为 -1，1 视为 1。问题转化为寻找最长的子数组，其元素和为 0。

这依然是前缀和的应用。若 sum[i] == sum[x-1]，则区间 [x, i] 的和为 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;
    }
};

8. 矩阵区域和

思路： 基于二维前缀和。对于矩阵中每个点 (i, j)，需要计算以它为中心、半径为 k 的矩形区域和。

关键在于处理边界：

• 左上角坐标：max(0, i-k), max(0, j-k)
• 右下角坐标：min(m-1, i+k), min(n-1, j+k)

注意 DP 表是 1-based 的，计算时需进行下标偏移。

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, 0));
        
        // 构建二维前缀和
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算有效边界并转换为 DP 表下标
                int x1 = max(0, i - k) + 1;
                int y1 = max(0, j - k) + 1;
                int x2 = min(i + k, m - 1) + 1;
                int y2 = min(j + k, n - 1) + 1;
                
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
};