本文共 2353 字，大约阅读时间需要 7 分钟。

一维前缀和和二维前缀和是解决常见数据查询问题的高效方法，能够显著提升程序性能。以下是详细的解释和应用示例。

一维前缀和

定义： 前缀和数组s[i]表示原数组a[1]到a[i]的和，且s[0]=0。

计算方式：

• 遍历数组，逐个累加元素得到前缀和数组。

查询方式：

• 区间和：s[R] - s[L-1]。

优点：

• 预处理时间O(N)。
• 查询时间O(1)。

应用示例：

import java.util.Scanner;
public class Main {
    static final int N = 100010;
    static int[] a = new int[N];
    static int[] s = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            s[i] = s[i-1] + a[i];
        }
        while (true) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(s[r] - s[l-1]);
        }
    }
}

优化示例：

public class Main {
    static final int N = 100010;
    static long[] s = new long[N];
    static int[] cnt = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            s[i] = s[i-1] + sc.nextInt();
        }
        long res = 0;
        cnt[0] = 1;
        for (int r = 1; r <= n; r++) {
            res += cnt[s[r] % k];
            cnt[s[r] % k]++;
        }
        System.out.print(res);
    }
}

二维前缀和

定义： 前缀和矩阵s[x][y]表示原矩阵中左上角到(x,y)的所有元素的和。

计算方式：

• s[x][y] = s[x-1][y] + s[x][y-1] - s[x-1][y-1] + a[x][y]。

查询方式：

• 子矩阵和：s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]。

应用示例：

public class Main {
    static final int N = 1010;
    static int[][] a = new int[N][N];
    static int[][] s = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
            }
        }
        while (q-- != 0) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
        }
    }
}

总结

前缀和技术通过预处理减少了每次查询的时间复杂度，使得处理大量数据更加高效。无论是一维还是二维前缀和，其核心思想都是利用预处理和数学优化来提升性能，广泛应用于数据查询和范围和问题中。

转载地址：http://hzhfk.baihongyu.com/