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

C++算法

前缀和算法详解与实战

前缀和是一种通过预处理数组来优化区间查询效率的经典技巧。核心思想是利用递推关系存储累积值，将区间求和时间复杂度从 O(N) 降至 O(1)。本文涵盖了一维与二维前缀和的构建原理及代码实现，重点解析了包含边界处理、负数取模修正等细节。结合 LeetCode 典型例题，如寻找中心下标、子数组乘积、和为 K 的子数组等场景，展示了如何将前缀和思想应用于哈希表配合解决复杂问题。掌握该算法能有效提升处理静态数组区间统计类问题的性能。

墨染流年发布于 2026/3/28更新于 2026/4/250 浏览

前缀和算法详解与实战

前缀和是一种通过预处理数组来优化区间查询效率的经典技巧。核心思想是利用递推关系存储累积值，将区间求和时间复杂度从 O(N) 降至 O(1)。本文涵盖了一维与二维前缀和的构建原理及代码实现，结合典型例题展示如何将该思想应用于哈希表配合解决复杂问题。

一维前缀和

算法思路

假设有一个数组 arr，我们想快速计算任意区间 [l, r] 的元素和。直接遍历需要 O(N)，而使用前缀和数组 dp，其中 dp[i] 表示 [0, i] 区间内所有元素的累加和（注意下标处理），就可以实现 O(1) 查询。

递推公式为：

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

当访问区间 [l, r] 时，区间和即为 dp[r] - dp[l-1]。这里要注意边界，通常为了方便处理，前缀和数组会比原数组多开一个位置，或者在逻辑上补全第 0 项。

代码实现

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

int main() {
    int n, q;
    cin >> n >> q;
    // 使用 n+1 大小，方便处理从 1 开始的索引
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];

    // 初始化前缀和数组，使用 long long 防止溢出
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + arr[i];
    }

    int l, r;
    while (q--) {
        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]

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

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        int total = 0;
        for (int x : nums) total += x;
        
        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            if (leftSum == total - leftSum - nums[i]) return i;
            leftSum += nums[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));
        // 构建二维前缀和
        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;
    }
};