算法模板精讲：一维与二维前缀和实现及原理

Java 实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        if (!scan.hasNext()) return;
        
        int n = scan.nextInt();
        int q = scan.nextInt();
        
        // 使用 long 防止溢出
        long[] arr = new long[n + 1];
        long[] dp = new long[n + 1];
        
        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt();
        }
        
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + arr[i];
        }
        
        while (q-- > 0) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
        }
    }
}

性能说明：预处理阶段时间复杂度为 O(N)，单次查询时间复杂度为 O(1)，空间复杂度为 O(N)。

二、二维前缀和

核心思路

二维前缀和一维类似，但处理的是矩阵区域求和。目标是快速求出以 (row1, col1) 为左上角、(row2, col2) 为右下角的矩形区域内元素之和。

1. 预处理：构建前缀和矩阵

为了简化边界判断，我们在原矩阵上方和左方各补一行/一列 0。这样 dp[i][j] 表示从 (1, 1) 到 (i, j) 所围成矩形的元素总和。

递推公式推导： dp[i][j] 的值等于当前元素加上其左侧和前侧的前缀和，但要注意重叠部分被加了两次，需要减去一次。

公式如下： dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1] (注：此处假设原矩阵下标从 0 开始，dp 表下标从 1 开始，需做坐标映射)

2. 查询：利用容斥原理

对于查询区域 (x1, y1) 到 (x2, y2)，我们需要从大矩形中减去多余的部分。

计算公式： Sum = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

代码实现

C++ 实现

#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, 0));
    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;
}

Java 实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if (!in.hasNext()) return;
        
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        
        int[][] arr = new int[n + 1][m + 1];
        long[][] dp = new long[n + 1][m + 1];
        
        // 读入数据
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        
        // 处理前缀和矩阵
        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-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
        }
    }
}

性能说明：预处理时间复杂度 O(N*M)，单次查询 O(1)。建议在实际编码中手动推导一遍公式，加深理解。

总结

前缀和是解决区间求和问题的基础工具。掌握其核心在于理解'预处理换查询'的思想，以及二维情况下的容斥原理应用。在遇到大量区间查询且数据范围允许预处理时，优先考虑此方案。