백준 - 구간 합 구하기

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        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[][] arr = new int[N + 1][N + 1];
        
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + Integer.parseInt(st.nextToken());
            }
        }
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int sum = arr[c][d] - arr[c][b - 1] - arr[a - 1][d] + arr[a - 1][b - 1];
            System.out.println(sum);
        }
    }
}

2차원 구간합 구하는 법

원하는 원소(i, j)에서 한 칸씩 뺀 직사각형 (i-1, j), (i, j-1) 2개를 더해준다. 그리고 중복이 되는 (i-1, j-1) 직사각형을 뺴주고 (i, j)의 원소값을 더해주면 우리가 원하는 직사각형 부분합이 나온다.