前缀和算法详解：一维、二维及哈希优化应用 | 极客日志

C++算法

前缀和算法详解：一维、二维及哈希优化应用

综述由AI生成系统讲解前缀和算法，涵盖一维与二维前缀和的基础构建与应用。通过寻找数组中心下标、除自身以外数组的乘积等经典例题，展示了如何利用前缀和优化时间复杂度。进一步结合哈希表解决子数组求和问题（如和为 K、可被 K 整除、连续数组），并延伸至矩阵区域和场景。内容包含解题思路、代码实现及复杂度分析，旨在帮助读者掌握前缀和的核心思想与变体技巧。

二进制发布于 2026/3/26更新于 2026/5/1119 浏览

前缀和算法详解：一维、二维及哈希优化应用

1. 一维前缀和

题目描述：

给定一个长度为 n 的整数数组 arr 和 q 个查询，每个查询由两个整数 l 和 r 组成，表示区间 [l, r]。请计算出每个区间内所有元素的和。

示例 1：

输入：arr = [1, 2, 3, 4, 5], q = 2, 查询区间为 [(1, 3), (2, 4)]
输出：[6, 9]
解释：区间 [1, 3] 的元素和为 1 + 2 + 3 = 6，区间 [2, 4] 的元素和为 2 + 3 + 4 = 9。

提示：

1 <= n, q <= 100000
-10000 <= arr[i] <= 10000

解题思路 对于本道题，我们可以提前预处理出一个前缀和数组 dp，通过前缀和数组快速求出某个区间所有元素的和。

前缀和数组 dp[i] 表示数组起始位置到第 i 个位置的所有元素和。其递推公式我们很容易得出：

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

计算区间 [l, r] 的所有元素的和：

sum = 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];

    // 预处理 dp 数组，long long 元素类型防止溢出
    vector<long long> ;
     ( i = ; i <= n; ++i) dp[i] = dp[i - ] + arr[i];

     l, r;
     (q--) {
        cin >> l >> r;
        cout << dp[r] - dp[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));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> vv[i][j];
    }

    // 预处理矩阵数组，long long 防溢出
    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] + vv[i][j] - dp[i - 1][j - 1];
    }

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

class Solution {
    public int pivotIndex(int[] nums) {
        // 预处理出前缀和、后缀和数组
        int n = nums.length;
        int[] f = new int[n]; // 数组起始位置的左侧
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] + nums[i - 1];
        
        int[] g = new int[n];
        for (int i = n - 2; i >= 0; --i) g[i] = g[i + 1] + nums[i + 1];
        
        // 遍历数组找到中心下标
        for (int i = 0; i < n; ++i) {
            if (f[i] == g[i]) return i;
        }
        return -1;
    }
}

class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int e : nums) sum += e;
        int leftSum = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (2 * leftSum == sum - nums[i]) return i;
            leftSum += nums[i];
        }
        return -1;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        for (int i = 1; i < n; ++i) f[i] = f[i - 1] * nums[i - 1];
        
        int[] g = new int[n];
        for (int i = n - 2; i >= 0; --i) g[i] = g[i + 1] * nums[i + 1];
        
        int[] ret = new int[n];
        for (int i = 0; i < n; ++i) ret[i] = f[i] * g[i];
        return ret;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] g = new int[n]; // 后缀积
        for (int i = n - 2; i >= 0; --i) g[i] = g[i + 1] * nums[i + 1];
        
        // 遍历修改 g[i]
        // pre 为 i 位置左侧元素的乘积
        int pre = 1;
        for (int i = 0; i < n; ++i) {
            g[i] *= pre;
            pre *= nums[i];
        }
        return g;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 哈希表记录前缀和及其出现的次数
        Map<Integer, Integer> hash = new HashMap<>();
        // 处理区间和为 K 的特殊情况
        hash.put(0, 1);
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; ++i) {
            // 计算 [0, i] 的前缀和
            sum += nums[i];
            // 查找和为 sum - k 的子数组的个数
            if (hash.containsKey(sum - k)) ret += hash.get(sum - k);
            // 将前缀和加入哈希表
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // 哈希表存储前缀和余数及其出现的次数
        Map<Integer, Integer> hash = new HashMap<>();
        // 处理区间元素和刚好被 K 整除，余数为 0 的特殊情况
        hash.put(0, 1);
        int ret = 0, sum = 0;
        for (int e : nums) {
            // 计算前缀和
            sum += e;
            // 对前缀和取模，注意在 C++ 中，余数可为负
            // 需要换算成非负以免影响结果
            int mod = (sum % k + k) % k;
            // 查找前缀和的余数为 mod 的子数组的个数
            if (hash.containsKey(mod)) ret += hash.get(mod);
            // 将余数加入哈希表
            hash.put(mod, hash.getOrDefault(mod, 0) + 1);
        }
        return ret;
    }
}

class Solution {
    public int findMaxLength(int[] nums) {
        // 哈希表存储的是 [0, i] 区间元素和及其下标 i
        Map<Integer, Integer> hash = new HashMap<>();
        // 处理前缀和刚好为 0 的情况
        hash.put(0, -1);
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; ++i) {
            // 将数组中的 0 看待成 -1
            sum += nums[i] == 0 ? -1 : 1;
            // 如果前缀和存在则更新结果，不存在再加入哈希表
            if (hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum));
            else hash.put(sum, i);
        }
        return ret;
    }
}

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        // 1. 初始化前缀和数组，需要多加一行多加一列
        int m = mat.length, n = mat[0].length;
        // dp[i][j] 代表矩阵 mat 从 [0][0] 到 [i-1][j-1] 的所有元素的和
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; ++i)
            for (int j = 1; j < n + 1; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];

        // 2. 使用前缀和数组求和
        int[][] ret = new int[m][n];
        for (int i = 0; i < m; ++i) {
            // 下标转换并且要进行越界情况的处理
            int x1 = Math.max(0, i - k) + 1;
            int x2 = Math.min(m - 1, i + k) + 1;
            for (int j = 0; j < n; ++j) {
                int y1 = Math.max(0, j - k) + 1;
                int y2 = Math.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;
    }
}