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

注意坐标映射关系：DP 表中的 (i, j) 对应原矩阵 matrix 中的 (i-1, j-1)。

递推方程推导：

sum[i][j] 表示从 (0, 0) 到 (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) 围成的区域，结合容斥原理可得： 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));
    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];

    while (q--) {
        int x1, y1, x2, y2;
        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)。对于每个位置 ret[i]，其值由两部分组成：nums[0]...nums[i-1] 的乘积 乘以 nums[i+1]...nums[n-1] 的乘积。利用前缀乘积的思想，用两个数组 f 和 g 分别记录左右两侧的乘积。

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] = g[i] * f[i];
        return ans;
    }
};

5. 和为 K 的子数组

思路： 设 sum[i] 为 [0, i] 的前缀和。若存在子数组 [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。即两数之差能被 n 整除，等价于两数对 n 取模结果相同。

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

思路： 与上一题类似，只需将等式改为同余关系。统计前缀和余数相同的次数。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0 % k] = 1;
        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 出现次数相同。可将 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;
    }
};

8. 矩阵区域和

思路： 基于二维前缀和，但需要处理边界条件。对于以 (i, j) 为中心、半径为 k 的区域，左上角坐标为 (max(0, i-k), max(0, j-k))，右下角坐标为 (min(m-1, i+k), min(n-1, j+k))。注意 DP 表与原矩阵的下标偏移关系。

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));
        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++) {
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(i + k, m - 1) + 1, 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;
    }
};