算法优选：前缀和技巧与应用 | 极客日志

C++算法

算法优选：前缀和技巧与应用

前缀和是处理区间查询的高效技巧，通过预处理将 O(N) 降为 O(1)。内容涵盖一维与二维前缀和的构建逻辑及递推公式，结合哈希表解决子数组求和、整除判定等问题。示例代码采用 C++ 实现，重点展示边界条件处理与空间优化策略，适用于各类算法面试场景。

热情发布于 2026/3/23更新于 2026/5/55 浏览

前缀和是一种通过预处理将区间查询复杂度从 O(N) 降至 O(1) 的经典技巧。核心思想是构建一个累加数组，利用递推关系快速计算任意区间的元素和。下面我们从一维到二维，结合具体场景展开讲解。

一维前缀和

假设有一个数组 arr，我们定义 dp[i] 为 [1, i] 区间内所有元素的和。根据定义，dp[i-1] 存储的是 [1, i-1] 的和，因此可以得到递推公式：

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

当需要查询区间 [l, r] 的和时，只需计算 dp[r] - dp[l-1] 即可。

#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);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + arr[i];
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

二维前缀和

对于矩阵中的区域求和问题，我们可以类比一维情况。为了简化边界处理，通常在矩阵外围添加一行和一列 0。这样，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]

查询左上角 (x1, y1) 到右下角 (x2, y2) 的区域和时，同样利用容斥原理：

结果 = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-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();
        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;
    }
};

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

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

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[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;
    }
};