누적 합

배열의 앞에서부터의 합을 미리 구해 두어, 임의 구간의 합을 O(1) 에 답하는 기법.

매번 구간을 직접 더하면 질의 1번에 O(N), 질의가 많으면 O(NQ)로 터진다. 누적 합을 한 번 O(N)에 만들어 두면 그 뒤로는 질의마다 O(1)이다.

1차원 누적 합

prefix[i] = a[0] + a[1] + ... + a[i] (0번부터 i번까지의 합)

구간 [l, r]의 합은

sum(l, r) = prefix[r] - prefix[l - 1]

l == 0일 때 prefix[l-1]이 없으니, prefix 배열을 1칸 밀어서(1-indexed) 두면 경계 처리가 깔끔하다.

기본 코드 구조

// 1-indexed 누적 합
int a[100001], prefix[100001];

void build(int n) {
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
}

int rangeSum(int l, int r) { // [l, r] 합
    return prefix[r] - prefix[l - 1];
}

2차원 누적 합

솔직히 1차원은 금방 받아들였는데, 2차원은 처음에 되게 어려웠다. 1차원처럼 “앞에서부터의 합”이라는 감으로 접근했다가, 직사각형 영역 합을 구하는 식에서 막혔다.

내가 막혔던 지점을 그대로 적어 보면 이렇다.

• S(r, c)를 “(0,0)부터 (r,c)까지 직사각형의 합”으로 두는 것까지는 자연스러웠다.
• 문제는 임의의 직사각형 (r1,c1) ~ (r2,c2)의 합을 어떻게 빼서 만드느냐였다. S(r2,c2)에서 위쪽과 왼쪽을 빼야 하는데, 빼는 두 영역이 왼쪽 위 모서리에서 겹친다는 걸 처음엔 못 봤다.

그래서 직접 작은 격자를 그려 놓고 손으로 칸을 색칠해 봤다. S(r1-1,c2)(위쪽 띠)와 S(r2,c1-1)(왼쪽 띠)를 둘 다 빼면, 두 띠가 겹치는 왼쪽 위 사각형이 두 번 빠진다는 게 그제서야 눈에 들어왔다. 그 한 번을 다시 더해 줘야 한다.

이게 결국 포함–배제다.

넓이 = S(r2,c2) - S(r1-1,c2) - S(r2,c1-1) + S(r1-1,c1-1)

마지막 + S(r1-1,c1-1)이 “두 번 빠진 모서리를 되돌려 주는” 항이다. 이 한 항의 의미를 손으로 칠해 보고 나서야 2차원 누적 합이 비로소 이해됐다.

기본 코드 구조 (2차원)

int a[1001][1001], S[1001][1001];

void build(int n, int m) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
}

// (r1,c1) ~ (r2,c2) 직사각형 합
int rectSum(int r1, int c1, int r2, int c2) {
    return S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1];
}

차분 (반대 방향)

누적 합의 짝으로 차분(difference array, imos법) 이 있다. “구간에 일괄로 값을 더하는” 연산이 여러 번 들어올 때, 시작 지점에 +v, 끝 다음 지점에 -v만 기록해 두고 마지막에 한 번 누적 합을 돌리면 모든 구간 업데이트가 O(N + Q)에 끝난다.