前缀和算法详解与实战 | 极客日志

C++算法

前缀和算法详解与实战

前缀和是处理区间查询的高效技巧，通过预处理将 O(N) 降为 O(1)。内容涵盖一维及二维前缀和原理，结合 LeetCode 经典题目如中心下标、乘积除自身、和为 K 的子数组等，展示哈希表与前缀和的结合应用。重点解析边界处理、负数取模修正及空间优化技巧，提供可直接运行的 C++ 代码示例。

林间仙子发布于 2026/3/25更新于 2026/4/231 浏览

前缀和算法详解与实战

前缀和是一种高效处理区间查询的预处理技巧。通过预先计算累积和，可以将单次查询的时间复杂度从 O(N) 降低到 O(1)。本文将深入讲解一维及二维前缀和的原理，并结合 LeetCode 经典题目展示其实际应用场景。

一维前缀和

核心思路

构建一个前缀和数组 dp，其中 dp[i] 表示原数组 arr 在 [1, i] 区间内所有元素的累加和。递推公式为：

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

利用该数组，可以在 O(1) 时间内求出任意区间 [l, r] 的和：

sum(l, r) = dp[r] - dp[l-1]

注意：为了简化边界处理，通常将数组下标从 1 开始，并在初始化时预留 dp[0] = 0。

代码实现

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];

    // 使用 long long 防止溢出
    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + arr[i];
    }

     (q--) {
         l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - ] << endl;
    }
     ;
}

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

result = sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1]

#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];

    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;
}

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

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;
    }
};

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;
    }
};

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 x : nums) {
            sum += x;
            int r = (sum % k + k) % k; // 修正负数取模
            if (hash.count(r)) ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

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;
    }
};

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++) {
                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;
    }
};