1、前缀和&二维前缀和

AcWing 795. 前缀和

AcWing 796. 子矩阵的和

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main=new Main();
        main.qianzhuihe();
    }

    int N=10010;
    int []sums=new int[N];
    int []num=new int[N];
    //前缀和
    void qianzhuihe() {
        Arrays.fill(sums,0);
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();

        for (int i = 0; i < n; i++)
            num[i]=in.nextInt();
        for (int i = 1; i <=n; i++)
            sums[i]=sums[i-1]+num[i-1];

        for (int i = 0; i < m; i++) {
            int l=in.nextInt();
            int r=in.nextInt();
            System.out.println(sums[r]-sums[l-1]);
        }
    }
}

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.zijuzheng();
    }

    //二维子矩阵的和
    void zijuzheng() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = in.nextInt();
            }
        }

        int [][]sums=new int[n+1][m+1];
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <= m; j++) {
                sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+nums[i-1][j-1];
            }
        }

        for (int i = 0; i < q; i++) {
            int x1, y1,x2,y2;
            x1 = in.nextInt();
            y1 = in.nextInt();
            x2 = in.nextInt();
            y2 = in.nextInt();
            System.out.println(sums[x2][y2]-sums[x2][y1-1]-sums[x1-1][y2]+sums[x1-1][y1-1]);
        }
    }
}