一维前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int q=sc.nextInt();
        int []a=new int[n+1];
        int []sum=new int[n+1];
        for(int i=1;i<=n;i++){
          a[i]=sc.nextInt();
          sum[i]=sum[i-1]+a[i];
        }
        for(int i=0;i<q;i++){
        int l=sc.nextInt();
        int r=sc.nextInt();
        System.out.println(sum[r]-sum[l-1]);
        }
        sc.close();
    }
}

二维前缀和

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
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

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 [][]sum=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();
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
          }
        }
        for(int i=0;i<q;i++){
          int x1=scan.nextInt();
          int y1=scan.nextInt();
          int x2=scan.nextInt();
          int y2=scan.nextInt();
          int res=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
          System.out.println(res);
        }
        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
24
25
26
27
28
29
30
31
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int q=scan.nextInt();
        int []a=new int[n+10];
        int []b=new int[n+10];
        int []c=new int[n+10];
        for(int i=1;i<=n;i++){
          a[i]=scan.nextInt();
          b[i]=a[i]-a[i-1];
        }
        for(int i=1;i<=q;i++){
          int l=scan.nextInt();
          int r=scan.nextInt();
          int d=scan.nextInt();
          b[l]+=d;
          b[r+1]-=d;
        }
        for(int i=1;i<=n;i++){
          c[i]=c[i-1]+b[i];
        }
        for(int i=1;i<=n;i++)
          System.out.print(c[i]+" ");
        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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

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+10][m+10];
        int [][]b=new int[n+10][m+10];
        int [][]c=new int[n+10][m+10];

        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
              a[i][j]=scan.nextInt();
              b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
          }
        }
        for(int i=1;i<=q;i++){
          int x1=scan.nextInt();
          int y1=scan.nextInt();
          int x2=scan.nextInt();
          int y2=scan.nextInt();
          int d=scan.nextInt();
          b[x1][y1]+=d;
          b[x2+1][y1]-=d;
          b[x1][y2+1]-=d;
          b[x2+1][y2+1]+=d;
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            b[i][j]=b[i][j]+b[i][j-1]+b[i-1][j]-b[i-1][j-1];
          }
        }
        for(int i=1;i<=n;i++){
          for(int j=1;j<=m;j++){
            System.out.print(b[i][j]+" ");
          }
          System.out.println();
        }
        scan.close();
    }
}