14. 구간합

여러 번 묻는 구간의 합을 매번 처음부터 더하면 한 질문에 최악 O(N) 시간이 든다. 누적합(prefix sum)은 앞에서부터의 합을 한 번 저장해 두고 두 누적값의 차이로 구간을 구한다. 전처리에 O(N) 시간·공간을 쓰고 이후 각 질문을 O(1)에 답한다. 배열의 값이 바뀌지 않고 질의가 많을 때 특히 유리하다.

합 배열 S의 정의

• A[0]부터 A[i]까지의 합

S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i];

합 배열은 기존의 배열을 전 처리한 배열로써 이런 식으로 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n) 에서 O(1)로 감소

인덱스	0	1	2	3	4	5
배열A	15	13	10	7	3	12
합배열 S	15	28	38	45	48	60

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i] (i >= 1, 0 기반 배열이라면 S[0] = A[0])

구간 합을 구하는 공식

S[j] - S[i-1] (i부터 j까지 포함, i=0이면 앞부분의 합을 0으로 취급)

왜 빼는가? S[j]는 A[0]부터 A[j]까지이고 S[i-1]은 A[0]부터 A[i-1]까지다. 둘의 차에는 앞부분이 사라지고 A[i]...A[j]만 남는다. 위 표에서 인덱스 2부터 4까지는 10+7+3=20이고, S[4]-S[1]=48-28=20이다. i=0에서 S[-1]을 읽으면 오류가 나므로 코드에서는 앞에 0을 둔 1 기반 누적합 배열을 쓴다.

• 구간 합을 예제

import java.util.Scanner;
public class 구간합구하기4_11659 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        long[] S = new long[N + 1]; // S[0] = 0
        for (int i = 1; i <= N; i++) {
            S[i] = S[i-1] + scan.nextInt(); //합배열 S를 만드는 공식
        }

        StringBuilder answer = new StringBuilder();
        for (int seq = 0; seq < M; seq++) {
            int i = scan.nextInt();
            int j = scan.nextInt();
            if (i < 1 || j > N || i > j) {
                throw new IllegalArgumentException("구간은 1 <= i <= j <= N 이어야 합니다");
            }
            long sum = S[j] - S[i-1];
            answer.append(sum).append('\n');
        }
        System.out.print(answer);
    }
}

2차원으로 확장: 사각형을 네 조각으로 생각하기

2차원 구간 합 배열 D[x][y]

D[x][y] = 원본 배열의 (0,0)부터 (x,y)까지 사각형 영역 안있는 수의 합

       **숫자배열A[i][j]**                                                        

	1	2	3	4
1	1	2	3	4
2	2	3	4	5
3	3	4	5	6
4	4	5	6	7

완성된 구간합 배열 D[i][j]

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

• 가로 구간 합 배열

D[1][j] = D[1][j-1] + A[1][j]

• 세로 구간 합 배열

D[i][1] = D[i-1][1] + A[i][1]

D[i][j]의 값을 채우는 구간 합 공식

D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j]

윗쪽 직사각형 D[i-1][j]와 왼쪽 직사각형 D[i][j-1]을 더하면 왼쪽 위 D[i-1][j-1] 영역이 두 번 들어간다. 한 번 빼고 현재 칸 A[i][j]를 더해야 한다. 기존 식은 A[i-1][j] 같은 원본 배열 값을 더해 누적 영역을 만들지 못했다. 첫 행·열의 경계를 간단히 처리하려면 D[0][j]와 D[i][0]을 0으로 둔다.

질문 사각형이 (r1,c1)부터 (r2,c2)까지라면 양 끝을 포함한 합은 다음과 같다.

D[r2][c2] - D[r1-1][c2] - D[r2][c1-1] + D[r1-1][c1-1]

전체 큰 직사각형에서 위쪽과 왼쪽을 빼면 왼쪽 위 교집합을 두 번 뺀 셈이므로 한 번 되돌려 더한다. 예를 들어 위 표의 원본에서 (2,2)부터 (3,4)까지는 3+4+5+4+5+6=27이고, D[3][4]-D[1][4]-D[3][1]+D[1][1]=42-10-6+1=27이다.

public class PrefixSum {
    public static void main(String[] args) {
        int[][] a = {{1,2,3,4}, {2,3,4,5}, {3,4,5,6}, {4,5,6,7}};
        int rows = a.length;
        int cols = a[0].length;
        long[][] sum = new long[rows + 1][cols + 1];

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i-1][j-1];
            }
        }

        int r1 = 2, c1 = 2;
        int r2 = 3, c2 = 4;

        long result = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];
        System.out.println(result); // 27
    }
}

rows와 cols를 따로 두어 직사각형 배열도 처리한다. sum[i][j]는 원본의 첫 i행·첫 j열의 합이므로 원본 인덱스는 a[i-1][j-1]이다. 바깥 반복문을 한 행씩 채울 때 필요한 위쪽 sum[i-1][j], 왼쪽 sum[i][j-1], 대각선 sum[i-1][j-1]은 이미 계산되어 있다. 전처리는 O(RC), 한 사각형 질의는 O(1), 저장 공간은 O(RC)다.

값이 바뀌는 배열에는?

누적합은 정적 데이터에 맞는다. 한 원소를 수정하면 그 뒤의 누적합들이 달라져 1차원에서는 최악 O(N), 2차원에서는 최악 O(RC)를 다시 계산해야 한다. 값 수정과 합 질의가 둘 다 자주 일어나면 펜윅 트리나 세그먼트 트리처럼 갱신과 질의를 나눠 처리하는 구조를 고려한다. 합이 int 범위를 넘을 수 있어 예제는 long으로 누적한다. 입력이 빈 행렬이거나 좌표가 범위를 벗어나면 조회 전에 별도 검증이 필요하다.