算法进阶：前缀和原理与实战应用 | 极客日志

C++算法

算法进阶：前缀和原理与实战应用

前缀和是处理区间查询的高效技巧，核心在于预处理累积值将单次查询降至 O(1)。涵盖一维与二维前缀和的推导公式及边界处理，并结合中心下标、子数组乘积、和为 K 的子数组、可被 K 整除子数组、连续数组及矩阵区域和等经典算法题，展示哈希表与前缀和结合的应用场景。重点讲解负数取模修正、空间优化及索引映射细节，提供完整的 C++ 实现代码与逻辑分析。

数字游民发布于 2026/3/15更新于 2026/4/251 浏览

算法进阶：前缀和原理与实战应用

前缀和算法详解

前缀和（Prefix Sum）是处理区间查询问题的经典技巧，核心思想是通过预处理将单次查询的时间复杂度从 O(n) 降至 O(1)。无论是数组的一维区间求和，还是二维矩阵的子区域统计，亦或是结合哈希表解决子数组计数问题，前缀和都是高频考点。

一维前缀和

假设有一个数组 arr，我们定义前缀和数组 dp，其中 dp[i] 表示从下标 0 到 i 的所有元素之和。为了处理边界情况（如查询从下标 0 开始的区间），通常采用 1-based indexing，即 dp[i] 存储 arr[1...i] 的和。

状态转移方程：

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

区间查询： 若要计算 [l, r] 区间的和，公式为 dp[r] - dp[l-1]。这里减去 dp[l-1] 是为了剔除 l 之前的部分。

代码实现：

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

int main() {
    int n, q;
    cin >> n >> q;
    // 使用 n+1 大小，下标从 1 开始，避免 l=1 时访问 dp[0] 越界
    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--) {
         l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - ] << endl;
    }
     ;
}

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

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

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

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    // 矩阵下标从 1 开始
    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 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] = 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;
                int y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
};