前缀和算法原理与实战应用详解

二、二维前缀和

1. 核心思路

二维前缀和是一维的扩展。我们需要处理的是矩形区域的求和。利用容斥原理，减去重复计算的部分。

公式：dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i-1][j-1] 查询区域 (x1, y1) 到 (x2, y2) 的和： sum = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

2. 初始化与边界

初始化时，第 0 行和第 0 列的值并不重要，因为计算过程中会用到 dp[i-1][...] 和 dp[...][j-1]，只要保证访问不越界即可。通常将 dp 数组大小设为 (n+1) x (m+1)。

3. 代码实现

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

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> arr(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; 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][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i - 1][j - 1];
        }
    }
    
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        long long sum = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
        cout << sum << endl;
    }
    return 0;
}

三、寻找数组的中心下标

1. 思路分析

中心下标定义为：左侧元素之和等于右侧元素之和。我们可以利用前缀和的思想，先计算总和，遍历时维护左侧和，右侧和即为 总和 - 左侧和 - 当前值。

2. 代码实现

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

四、除自身以外数组的乘积

1. 思路分析

题目要求输出数组中每个位置除了自身以外所有元素的乘积。这可以看作是两个数组的乘积：一个是当前位置左侧所有数的乘积（左前缀），另一个是右侧所有数的乘积（右后缀）。

2. 代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n), ret(n);
        
        f[0] = 1; // 左边第一个没有元素，乘积为 1
        g[n - 1] = 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];
        }
        
        // 合并结果
        for (int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};

五、和为 K 的子数组

1. 思路分析

暴力枚举子数组是 O(n^2)。利用前缀和可以将问题转化为：寻找两个下标 i, j，使得 prefix[j] - prefix[i] = k，即 prefix[i] = prefix[j] - k。 使用哈希表存储前缀和出现的次数，遍历过程中直接查询是否存在 sum - k。

2. 代码实现

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

六、和可被 K 整除的子数组

1. 思路分析

基于上一题的思路，条件变为 (prefix[j] - prefix[i]) % k == 0，即 prefix[j] % k == prefix[i] % k。 注意负数取模的处理：(a % k + k) % k 确保余数为正。

2. 代码实现

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

七、连续数组

1. 思路分析

将数组中的 0 视为 -1，问题转化为寻找最长的子数组，其和为 0。同样使用前缀和 + 哈希表，记录每个前缀和第一次出现的位置。

2. 代码实现

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1; // 前缀和为 0 时，索引视为 -1
        int sum = 0, len = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if (hash.count(sum)) {
                len = max(len, i - hash[sum]);
            } else {
                hash[sum] = i; // 只记录第一次出现的位置
            }
        }
        return len;
    }
};

八、矩阵区域和

1. 思路分析

这是二维前缀和的直接应用。对于矩阵中的每个点 (i, j)，需要计算以它为中心，半径为 k 的矩形区域内的和。关键是确定矩形的四个边界坐标，并映射到前缀和数组上。

2. 代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> arr(m + 1, vector<int>(n + 1));
        
        // 构建二维前缀和
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        
        vector<vector<int>> arr1(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算矩形边界，注意映射到前缀和数组需 +1
                int x1 = max(0, i - k) + 1;
                int x2 = min(m - 1, i + k) + 1;
                int y1 = max(0, j - k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                
                arr1[i][j] = arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1];
            }
        }
        return arr1;
    }
};