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

2차원 배열의 구간합을 구하는 문제입니다.

1024*1024의 배열을 총 10만번의 반복을 할 수 있으므로 매번 for문으로 탐색하게 되면 시간초과가 발생합니다.
2차원 배열에 대한 누적합을 계산해주었습니다.

예를 들어 (3,2)는 (1,1), (1,2), (2,1), (2,2), (3,2)의 합을 가지고 있습니다.
(a,b) ~ (c,d)의 구간합을 구하기 위해서 (c,d) - (c, b-1) - (a-1, d) + (a-1, b-1)을 해주었습니다. ((c,d)가 (a,b)보다 큼)

(map[y2][x2] - map[y2][x1-1] - map[y1-1][x2] + map[y1-1][x1-1])

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] map = 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) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num + map[i-1][j] + map[i][j-1] - map[i-1][j-1];
			}
		}
		for(int i=0; i<m; ++i) {
			st = new StringTokenizer(br.readLine());
			int y1 = Integer.parseInt(st.nextToken());
			int x1 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			bw.write((map[y2][x2] - map[y2][x1-1] - map[y1-1][x2] + map[y1-1][x1-1]) + "\n");
		}
		bw.close();
	}
}