前缀和算法详解与经典例题解析 | 极客日志

C++算法

前缀和算法详解与经典例题解析

详细讲解了一维和二维前缀和算法的原理及实现，并通过六个经典力扣（LeetCode）例题展示了前缀和及其变体在区间求和、中心下标查找、乘积计算、子数组统计等场景中的应用。内容涵盖预处理技巧、边界处理、哈希表优化及负数取余修正，旨在帮助读者掌握 O(1) 查询区间和的高效解法。

虚拟内存发布于 2026/3/25更新于 2026/4/184 浏览

前缀和算法详解与经典例题解析

一维前缀和

题目链接: 牛客网

描述给定一个数组，进行多次区间求和查询。

输入描述 第一行包含两个整数 n, q。n 表示数组大小，q 表示查询次数。接下来一行 n 个整数表示数组元素。接下来 q 行，每行两个整数 l, r，表示查询区间。

输出描述 输出 q 行，每行代表一次查询的结果。

示例输入： 3 2 1 2 4 1 2 2 3

输出： 3 6

该题第一行输入 3 2 的意思是数组大小为 3，需进行 2 次查询。第二行输入的 n 个整数表示数组中的元素。后面的 2 行是计算数组中从 l 到 r 的和。

如果使用暴力解法解决这个题，时间复杂度会超时。因此需要使用前缀和算法，可以快速得出某一段区间之和的大小，时间复杂度为 O(1)。

第一步：预处理出来一个前缀和数组 dp。 dp[i] 表示 [1, i] 区间内所有元素的和。 dp[3] 表示数组第一个元素到第三个元素的和。递推公式：dp[i] = dp[i-1] + arr[i]

疑问：为什么我们的 dp 下标从 1 开始计数？假设我们想求出 [0, 2] 区间的大小，利用 dp 得到 dp[2] - dp[-1]，这会导致越界。如果从 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];
    
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
    
    int l = 0, r = 0;
    while (q--) {
        cin >> l >> r;
        cout << dp[r] - dp[l - ] << endl;
    }
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

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

int main() {
    int n = 0, m = 0, q = 0;
    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] + arr[i][j] - dp[i - 1][j - 1];
        }
    }
    
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while (q--) {
        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);
        // 1. 预处理前缀和数组以及后缀和数组
        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];
        }
        // 2. 使用，枚举所有的中心下标
        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), g(n);
        // 1. 预处理前缀积数组和后缀积数组
        f[0] = g[n - 1] = 1;
        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];
        }
        // 使用前缀积数组和后缀积数组
        vector<int> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};

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(m - 1, i + k) + 1, 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;
    }
};