BOJ 2042. 구간 합 구하기를 해결하는 것이 이 글의 목표입니다.

문제를 요약하면 다음과 같습니다:

길이 N의 배열 A가 주어질 때, 다음 두 쿼리를 처리하자.

1. 1 i v : A[i] = v; (1 ≤ i ≤ N)
2. 2 l r : (A[l] + A[l+1] + ... + A[r]) 를 계산

N ≤ 1,000,000 이고, (쿼리의 개수) ≤ 20,000 이다.

두 연산은 일단 다음과 같이 단순하게 처리할 수 있습니다.

int A[N+1];

void update(int i, int v) {
		A[i] = v;
}

int query(int l, int r) {
		int ans = 0;
		for(int i = l; i <= r; i++) ans += A[i];
		return ans;
}

이러한 나이브한 방식은 2번 쿼리를 한 번 수행할 때 최대 N번의 연산을 수행하게 됩니다.

즉, 쿼리의 개수를 Q개라 했을 때, 문제를 O(QN)의 시간복잡도로 해결합니다.

안타깝게도 문제의 제한에 따르면 QN ≤ 20,000,000,000 이므로 시간 내에 해결할 수 없습니다.

어떻게 하면 2번 쿼리를 O(N) 미만에 해결할 수 있을까요?

graph TD
  1["1~8"] --> 2["1~4"]
  1 --> 3["5~8"]
  2 --> 4["1~2"]
  2 --> 5["3~4"]
  4 --> 8["1"]
  4 --> 9["2"]
  5 --> 10["3"]
  5 --> 11["4"]
  3 --> 6["5~6"]
  3 --> 7["7~8"]
  6 --> 12["5"]
  6 --> 13["6"]
  7 --> 14["7"]
  7 --> 15["8"]

위와 같은 이진 트리 구조를 생각해 봅시다.

그림에서 사각형은 트리의 노드를, 화살표는 자식 관계를 의미하며, 쓰여 있는 수는 각 노드가 관리하는 인덱스 범위를 나타냅니다.

두 자식 노드는 부모 노드가 관리하는 범위를 절반씩 나눠 가지게 됩니다.

이때, 이 트리의 높이는 $\log_2N$ 임을 쉽게 알 수 있습니다.

이제, 범위 l ~ r의 노드는 A[l] + ... + A[r]의 값을 담고 있다고 가정해 봅시다.

1번 쿼리의 경우, 값을 변경해야 되는 노드는 각 층에 하나만 있습니다.