1. 문제 설명

2. 접근 방식

sum[i] [j] = (0,0) ~ (i,j) 까지의 합으로 나타냈다.
i = 0 인 열은 이전 행의 최대 값을 저장하도록 해서, 누적합이 계속 이어지도록 만들었다.
하지만 구간 합 (a,b) ~ (c,d)를 구하라 함은, a < x < c , b < y < d 의 인덱스를 가진 배열들의 합을 구하란 말이다. 따라서 단순한 누적 합이 아닌, 배열 안의 네모난 부분을 구해야 한다. 예를 들면

그래서 나는 다음과 같이 구했다.

다음과 같이 푸른색 형광펜에서 보라색 형광펜 값을 빼주고 그 결과들을 더 했다.

3. 코드 분석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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 [][] s = new int [N+1][N+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= N; j++) {
                s[i][j] = j==0? s[i-1][N] : s[i][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int sX = Integer.parseInt(st.nextToken());
            int sY = Integer.parseInt(st.nextToken());
            int eX = Integer.parseInt(st.nextToken());
            int eY = Integer.parseInt(st.nextToken());

            int sum = 0;

            for (int j = sX; j <= eX; j++) {
                sum += (s[j][eY] - s[j][sY-1]);
            }

            sb.append(sum).append("\n");
        }

        System.out.println(sb);
    }
}

(1) 아쉬운 점

구간 합을 구하는데, 반복문이 들어가서 느리다. M^2는 아니지만, 그래서 최악의 경우에는 M*N의 시간복잡도가 든다. N = 1024 이지만, M = 10^5 여서 가까스로 1억 번 연산 안 쪽으로 들어올 것 같다.

4. 성장 하기

해당 문제에서 원하는 구간합이 네모난 배열의 부분을 구하라는 뜻이므로, 그것을 이용하여, 누적 합을 다르게 생각해본다.

푸른색 형광펜이 칠해진 범위까지의 누적합을 생각해보면,
$$
(초록색 형광펜 + 빨간색 형광펜 - 겹치는 부분) + 푸른색 형광펜의 원래 값
$$
이다.
이를 공식으로 표현하면,
$$
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]
$$
이다.
이런 식으로 누적합 또한 (0,0) ~ (i, j) 까지의 네모난 누적 합의 개념으로 바꿔 생각한다. 그러면 누적합 배열의 값은 다음과 같이 채워진다.

이제 여기서 원하는 구간 합을 구하려면 어떻게 해야할까?
만약 (3,3) ~ (4,4) 누적합을 구해야 한다면 다음과 같이 구할 수 있을 것이다. 먼저 일반 배열에서 생각해보자

파란색 부분을 구하려면 전체 누적합 - 초록색 부분 (가로) - 초록색 부분 (세로) + 초록색 겹치는 부분 이다.
이를 누적합에서 보면

빨간색 - (초록색 1 + 초록색 2) + 주황색 이다.
수식으로 표현 하면, ((startX, startY) ~ (endX,endY) 까지의 구간 합 구하기)
$$
sum[endX][endY] - (sum[startX-1][endY] + sum[endX][startY-1])+sum[startX-1][startY-1]
$$
이다.
이를 이제 코드로 구현하면 된다.

5. 다시 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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 [][] sum = 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++) {
                    sum[i][j] = sum[i][j-1] + sum[i-1][j]  - sum[i-1][j-1] + Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());

            sb.append((sum[ex][ey] - sum[ex][sy-1] - sum[sx-1][ey] + sum[sx-1][sy-1])).append("\n");
        }
        System.out.println(sb);
    }
}