前缀和算法核心原理与实战应用 | 极客日志

C++算法

前缀和算法核心原理与实战应用

综述由AI生成前缀和是一种通过预处理数组来快速计算区间和的技术。详细讲解了前缀和一维与二维的核心公式，以及利用哈希表优化的子数组求和问题。内容涵盖中心下标查找、乘积除自身、定和子数组、整除判断及矩阵区域和等经典场景。通过对比暴力解法，展示了如何将时间复杂度从 O(n^2) 降至 O(n)，并提供了完整的 C++ 实现代码与边界处理技巧。

BigDataPan发布于 2026/3/22更新于 2026/5/1111 浏览

前缀和算法核心原理与实战应用

前缀和算法核心原理与实战应用

前缀和（Prefix Sum）是处理区间查询问题的经典技巧，通过预处理将单次查询的时间复杂度从 O(n) 降至 O(1)。本文将深入讲解一维与二维前缀和的推导过程，并结合哈希表优化解决子数组求和等进阶问题。

一、一维前缀和模板

核心思路

暴力解法每次查询都遍历区间，时间复杂度为 O(q*n)。使用前缀和数组 sum，其中 sum[i] 存储原数组下标 1 到 i 的元素累加和。计算区间 [l, r] 的和时，只需 sum[r] - sum[l-1]。

为了简化边界处理，通常将前缀和数组开大一位，令 sum[0] = 0，这样当 l=1 时，sum[l-1] 即 sum[0] 不会越界。

前缀和一维示意图

C++ 实现

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

int main() {
    int n = 0, q = 0; 
    cin >> n >> q;
    
    vector<long long> sum;
    sum.reserve(n + 1);
    sum.push_back(0); // sum[0] = 0

    for (int i = 1; i <= n; i++) {
        int num = 0;
        cin >> num;
        sum.push_back(sum.back() + num);
    }

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

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

int main() {
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;

    vector<vector<int>> vv(n + 1, vector<int>(m + 1));
    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++)
            cin >> vv[i][j];

    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] + vv[i][j];
        }
    }

    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1, 0), g(n + 1, 0);
        
        for (int i = 0; i < n; i++) f[i + 1] = f[i] + nums[i];
        for (int i = n - 1; i >= 0; i--) g[i] = g[i + 1] + nums[i];

        for (int i = 0; i < n; i++) {
            if (f[i] == g[i + 1]) return i;
        }
        return -1;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1, 1), g(n + 1, 1);
        
        for (int i = 0; i < n; i++) f[i + 1] = f[i] * nums[i];
        for (int i = n - 1; i >= 0; i--) g[i] = g[i + 1] * nums[i];

        vector<int> ans;
        for (int i = 0; i < n; i++) ans.push_back(f[i] * g[i + 1]);
        return ans;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> um;
        um[0] = 1; // 处理前缀和直接等于 k 的情况
        int count = 0, sum = 0;
        
        for (int num : nums) {
            sum += num;
            if (um.count(sum - k)) count += um[sum - k];
            um[sum]++;
        }
        return count;
    }
};

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> um;
        um[0] = 1;
        int count = 0, sum = 0;
        
        for (int num : nums) {
            sum += num;
            int mod = (sum % k + k) % k;
            if (um.count(mod)) count += um[mod];
            um[mod]++;
        }
        return count;
    }
};

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> um;
        um[0] = -1;
        int maxLen = 0, sum = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if (um.count(sum)) maxLen = max(maxLen, i - um[sum]);
            else um[sum] = i;
        }
        return maxLen;
    }
};

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        vector<vector<int>> ans(n, vector<int>(m));

        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] + mat[i - 1][j - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int x1 = max(i - k, 1), y1 = max(j - k, 1);
                int x2 = min(i + k, n), y2 = min(j + k, m);
                ans[i - 1][j - 1] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
            }
        }
        return ans;
    }
};