题解 | 【模板】二维前缀和

这个题想让我们求一个二维数组的和，由于数据量大，不好直接遍历求，我们采用二维前缀和

也就是把每一行的单独作为一个一维数组，求出这个一维数组对应的前缀和数组，然后扩展到二维数组

后面直接通过前缀和的套路去求解即可

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		int q=scanner.nextInt();
		long a[][]=new long[n][m];
		long sum[][]=new long[n][m+1];
		for (int i = 0; i < a.length; i++) {
//			二维数组下面的边界应当是a[0].lenth
			for (int j = 0; j < a[0].length; j++) {
				a[i][j]=scanner.nextLong();
				sum[i][j+1]=sum[i][j]+a[i][j];
			}
		}
		
		while(q-->0) {
			long s=0;
			int x1=scanner.nextInt();
			int y1=scanner.nextInt();
			int x2=scanner.nextInt();
			int y2=scanner.nextInt();
			for (int i = x1-1; i < x2; i++) {
				s=s+sum[i][y2]-sum[i][y1-1];
			}
			System.out.println(s);
			
		}
		
		

	}

}