[백준 11660] 구간 합 구하기 5

 

이차원 배열의 구간합이다.

 

예제의 구간합 배열은 다음과 같다.

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

 

 

 

사각형 넓이 구할때와 마찬가지로

 

부분합 C = (A+B) + (A+B) - A = A + 2B 이다.

위 식대로 하면 표대로 배열의 값을 채워 넣을 수 있고 구간별 합을 구할때도 위 식을 활용한다.

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int a[][] = new int[n][n];
        int psum[][] = new int[n+1][n+1];
        
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
                psum[i+1][j+1] = psum[i][j+1] + psum[i+1][j] - psum[i][j] + a[i][j];
            }
        }
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            System.out.println(psum[x2][y2] - psum[x1-1][y2] - psum[x2][y1-1] + psum[x1-1][y1-1]);
        }
    }
}