前缀和的总结java版本_前缀和算法 java

概念

前缀和要求下标从1开始，可以避免下标的转换，对于a[0]的处理：赋值为0即可，从而S[1] = a[0] + a[1] = 0 + a[1] = a[1]；S[2] = a[0] + a[1] + a[2] = 0 + a[1] + a[2] = a[1] + a[2]。对于S[N]，a[N]数组可以定义为全局变量，这样a[0]初始值就为0，通过前缀和可以轻松知道某段范围数组的元素和的

一维数组求前缀和

        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
1
2
3

本题就是前缀和的简单应用，可以快速求出询问区间范围的总合：以下为其代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] a = new int[n + 1];
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scan.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + a[i];
        }
        while (m-- > 0) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            System.out.println(s[r] - s[l - 1]);
        }
        scan.close();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二维数组的前缀和计算

而对于二维数组的范围和，前缀和更是好用：

s[i, j] = s[i, j - 1] + s[i - 1, j] - s[i - 1, j - 1] + a[i, j];
可以通过图示轻易得到
1
2

求（x1，y1），（x2，y2）子矩阵的和
可以得到表达式：

区域的面积为：s[X2, Y2]-s[X2, Y1-1]-s[X1-1, Y2]+s[X1-1, Y1-1]
1

import java.util.*;

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

//需要注意的是x和y的范围是多少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class NumMatrix {

    int [][]a;
    int [][]s;

    public NumMatrix(int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        a=new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = matrix[i-1][j-1];
            }
        }
        s = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return s[row2+1][col2+1]-s[row2+1][col1]-s[row1][col2+1]+s[row1][col1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26