BOJ11660 구간 합 구하기 5(R) *

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

 

2차원 구간합은 원점으로부터의 사각형의 합을 이용한다.

import java.util.*;
import java.io.*;
public class Main
{   
    static int[][] map;
    static int[][] plusmap;
    static int n;
    public static void pre(){
        for(int i =1; i<n+1; i++){
            for(int j=1; j<n+1;j++){
                plusmap[i][j] = plusmap[i-1][j]+plusmap[i][j-1]-plusmap[i-1][j-1]+map[i-1][j-1]; ;
            }
        }
    }
    
    public static int calc(int x1, int y1, int x2, int y2){
        int ans = plusmap[x2][y2]-plusmap[x1-1][y2]-plusmap[x2][y1-1]+plusmap[x1-1][y1-1];
        return ans ;
        
    }
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    String[] input1 = br.readLine().split(" ");
	    n = Integer.valueOf(input1[0]);
	    int m = Integer.valueOf(input1[1]);
	    map = new int[n][n];
	    plusmap = new int[n+1][n+1];
		for(int i =0; i<n;i++){
		    String[] temp = br.readLine().split(" ");
		    for(int j=0;j<n;j++){
		        map[i][j] = Integer.valueOf(temp[j]);
		    }
		}
		
		
		pre();
		
		for(int i=0; i< m;i++){
		    String[] temp = br.readLine().split(" ");
		    
		    bw.write(calc(Integer.valueOf(temp[0])
		        ,Integer.valueOf(temp[1])
		        ,Integer.valueOf(temp[2])
		        ,Integer.valueOf(temp[3]))+"\n");
		    
		    
		}
		bw.flush();
	}
}