서론
구간합이란 임의의 배열 $a_1, a_2, \dots, a_N$에서 쿼리 $(x, y)$가 주어지면 $S = a_x + a_{x+1} + \dots + a_y = \sum_{i=x}^{y}{a_i}$인 $S$의 값을 구하는 것이다. 구간합 문제는 일상 속에서도 많이 발견할 수 있을 뿐만 아니라 다양한 분야에서 사용된다.
간단해 보이는 이 문제는 한 쿼리가 주어질 때 마다 $O(y - x + 1)$의 복잡도를 가지고 있기 때문에 $Q$개의 쿼리가 주어질 때, 최악의 경우 $O(NQ)$만큼의 비용이 든다.
이 문제를 빠르게 해결할 수는 없을까?
누적 합 배열 - Prefix Sum Array
구간합을 구해야 하는 배열 $a_i$의 각 원소의 값이 고정되어 있다면 $O(N)$의 전처리를 통해 각 쿼리를 $O(1)$만에 처리할 수 있다.
전처리에서 구하는 것이 바로 Prefix Sum Array이다. 예를 들어 다음의 경우를 보자.
| $i$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $a_i$ | 3 | 2 | 4 | 7 | 1 |
위 배열에 대한 Prefix Sum Array는 다음과 같다.
| $i$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $S_i$ | 3 | 5 | 9 | 16 | 17 |
즉, $S_{i+1} = a_0 + a_1 + \dots + a_i + a_{i+1} = a_{i+1} + \sum_{j=0}^{i}{a_j} = a_{i+1} + S_{i}$이다. 배열 $S_i$는 메모이제이션을 통해 $O(N)$만에 구할 수 있음은 자명하다.
그렇다면 $\sum_{i=x}^{y}{a_i} = \sum_{i=0}^{y}{a_i} - \sum_{i=0}^{x - 1}{a_i} = S_y - S_{x-1}$임을 이용해 각 쿼리를 $O(1)$만에 처리할 수 있음을 알 수 있다.
이를 통해 모든 쿼리를 $O(N + Q)$만에 처리할 수 있다. 대부분의 경우가 $N < Q$인 상황이므로, $O(NQ)$보다 큰 이득을 본다.
하지만, 배열 $a_i$에서 한개 이상의 원소의 값이 업데이트(증가 또는 감소)되어야 하는 상황이 발생하면 Prefix Sum Array를 다시 구해야 한다. 만약 각 쿼리마다 배열의 원소가 업데이트 되어야 하는 상황이라면, Prefix Sum Array를 사용하지 못한다.
세그먼트 트리 - Segment tree
Segment tree는 트리의 각 노드에 구간을 할당하고, 각 구간에 대한 정보를 담고 있도록한 자료구조다.
Segment tree는 Binary tree이다. 다음의 Binary tree를 생각해 보자.
각 노드에 적혀있는 번호를 해당 노드의 인덱스로 하자. Root노드는 배열 전체 구간을 관리한다. 이후 두 자식 노드는 부모 노드의 관리 구간을 반씩 나누어 관리한다. 이에 따라 각 leaf노드는 배열에 속한 하나의 원소만 관리한다. 즉, 각 노드의 depth가 1씩 증가할 수록 노드가 관리하는 구간은 $\frac{1}{2}$배 줄어든다.
위에 보인 Binary tree의 leaf노드의 개수는 4개 이므로 배열의 길이가 4인 배열을 표현할 수 있다. 다음은 각 노드가 관리하는 구간과 배열의 인덱스를 표현한 그림이다.
각 노드는 다음과 같이 “관리”된다.
- 각 노드는 자신이 관리하는 구간의 부분합을 저장한다.
- 자신이 관리하는 구간에 속한 원소 한개의 값이 $dv$만큼 변화했다면, 자신이 가지고 있는 부분합 값 또한 $dv$만큼 변화시킨다.
위와 같이 관리되면 각 노드는 자신이 관리하는 구간의 부분합을 업데이트가 발생한 경우에도 정확하게 가지고 있다.
그렇다면 다음의 상황에서 두 가지 연산 (부분합을 구하는 연산, 원소를 업데이트하는 연산)을 구현해 보자.
위의 그림은 배열에 속한 값과 해당 배열을 표현하고 있는 segment tree를 보이고 있다.
위의 그림에서 쿼리 $(0, 3)$가 주어지면 노드 1의 값인 13을 반환하면 된다. 마찬가지로 $(0, 1)$이 주어지면 노드 2의 값인 3을 반환하면 된다. $(1, 2)$와 같이 관리중인 구간에 딱 떨어지지 않는 경우는 노드 5의 값과 노드 6의 값의 합을 반환한다.
트리의 각 레벨에서 최대로 선택될 수 있는 노드는 4개 이고(이는 각 레벨에서 연속하는 노드 4개를 선택해 보면 알 수 있다), 최대 leaf노드까지 탐색이 이루어 지므로 $O(\log{N})$에 구간합을 수행한다.
이제 배열의 원소의 값이 업데이트 되는 경우를 보자. 다음은 배열 인덱스 2를 포함하여 관리하는 노드들을 나타낸 그림이다.
위에 표현되는 노드들의 값만 처리해주면 업데이트 이후의 배열을 정확히 표현할 수 있다. 만약 인덱스 2의 원소의 값이 $dv$만큼 변화했다면 인덱스 2의 원소를 포함하는 모든 노드의 값 또한 $dv$만큼 변화시켜주면 된다. 이는 하나의 leaf노드에서 부터 root노드까지 타고 올라가는 과정과 동일하므로 $O(\log{N})$에 해결된다.
그런데 Segment tree는 Prefix Sum Array와는 다르게 비선형 구조이다. 따라서 공간 복잡도가 더 높다. 만약 $N$이 2의 제곱수라면 즉, $\log_2{N} \in \mathbb{N}$이면 필요한 노드의 개수는 leaf노드의 개수가 $N$인 Binary tree의 노드 개수와 동일하므로 $N + \sum_{i=0}^{h-1}{2^i}=N + \frac{2^h-1}{2-1}=N + 2^h - 1$만큼이 필요하고, 트리의 높이인 $h$은 $\log_2{N}$이므로 $N + 2^h - 1 = 2N - 1$임을 알 수 있다. $\log_2{N} \notin \mathbb{N}$인 경우, $\sum_{i=0}^{\left \lceil \log_2{N} \right \rceil}2^i = 2^{\left \lceil \log_2{N} \right \rceil+1}-1 = 4N - 1$이므로 $4N$정도의 공간이 필요하다.
정리하자면, segment tree는 구간합을 구하는 query연산과 원소 하나에 대한 값 업데이트를 모두 $O(\log{N})$에 수행한다. 따라서 segment tree를 이용하면 원소 하나씩 업데이트가 되는 상황에서 모든 쿼리를 $O(N+Q\log{N})$만에 처리한다.
펜윅 트리 - Fenwick Tree
Fenwick tree는 일반적인 트리의 형태와는 다르다. Binary Indexed Tree 줄여서 BIT라고도 불리는 Fenwick tree는 이진수의 주기적 특성을 이용하여 부분합 $O(\log{N})$에 처리한다.
예를 들어서 인덱스 1에서 부터 시작하는 배열 $b_i$에 대해 $b_1+b_2+\dots+b_7$의 값을 구한다고 하자. 이는 다음과 같이 표현할 수 있다.
\[b_7+(b_6+b_5)+(b_4+b_3+b_2+b_1)\]만약 $(b_6+b_5)$의 값과 $(b_4+b_3+b_2+b_1)$값을 각각 $O(1)$에 가져올 수 있다면 $b_1+b_2+\dots+b_7$를 구하는 데에 $O(\log{7})$정도만 소요될 것이다.
그렇다면 미리 가지고 있어야 하는 구간을 어떻게 정할까? 앞의 예제에서 묶은 각 구간의 길이를 다음과 같이 풀어보자.
\[1 + 2 + 4 = 1\times2^0+1\times2^1+1\times2^2\]2진수로 표현했을 때 1로 표현되는 각 자리수의 값만큼 묶은 부분합을 미리 가지고 있으면 된다. 이러한 관찰을 바탕으로 각 인덱스 $x$에 대해 가지고 있어야할 부분합 구간의 크기 $L(x)$는 다음과 같다.
- $L(1)=L(1_{(2)})=1$
- $L(2)=L(10_{(2)})=2$
- $L(3)=L(11_{(2)})=1$
- $L(4)=L(100_{(2)})=4$
- $L(5)=L(101_{(2)})=1$
- $L(6)=L(110_{(2)})=2$
- $L(7)=L(111_{(2)})=1$
- $L(8)=L(1000_{(2)})=8$
- $L(9)=L(1001_{(2)})=1$
- $L(10)=L(1010_{(2)})=2$
- $\dots$
즉, 2진수로 표현했을 때 가장 먼저 등장하는 1의 자리수 값을 구간의 크기로 가진다. 이를 그림으로 표현하면 다음과 같다.
각 인덱스 $x$가 가지고 있는 구간합을 $F(x)$라고 하면 다음과 같다.
\[\sum_{i=1}^{k}{b_i}=\sum_{i=0}^{\left \lfloor \log_2{k} \right \rfloor}{\left (\left \lfloor \frac{k}{2^i} \right \rfloor \mod{2} \right) \times F \left (\left \lfloor \frac{k}{2^i} \right \rfloor\times 2^i \right)}\]앞서 예를 든 경우에 대해 식을 전개하면 다음과 같다.
\[F(7) + F(6) + F(4) = F(111_{(2)}) + F(110_{(2)}) + F(100_{(2)})\]$k=9$인 경우는 다음과 같다.
\[F(9) + F(8) = F(1001_{(2)}) + F(1000_{(2)})\]결국 임의의 $k$에 대해, 필요한 $F(x)$의 개수는 최대 $O(\log{k})$임을 알 수 있다. 이에 따라 쿼리 $(x, y)$가 주어지면 $k=x - 1$와 $k=y$인 경우 각각을 구해 구간합을 $O(\log{N})$에 구할 수 있다.
이제 업데이트 하는 경우를 살펴보자. 인덱스 $x$에 대한 업데이트 연산이 주어졌을 경우, 인덱스 $x$를 관리하고 있는 구간 내에 포함하고 있는 인덱스는 $x$보다 큰 인덱스임은 자명하다. 또한 $x \lt i \lt x + L(x)$인 $i$의 경우 $L(x) \gt L(i)$이므로 $i - L(i) + 1 \gt x$를 만족하여 $x$를 구간으로 가지지 않는다. 반면 $i=x+L(x)$의 경우 $L(i) \geq L(x)$이므로 $i - L(i) + 1 \leq x$를 만족하여 $x$를 구간으로 포함한다. $i \gt x + L(x)$의 경우는 $x + L(x)$에 대해서만 고려를 해주면 된다. $x + L(x)$를 포함하지 못하는 $i$는 자연히 $x$도 포함하지 못하기 때문이다.
따라서 $x$를 업데이트하는 연산이 주어진 경우, $x$를 업데이트 하고 $x + F(x)$를 업데이트하는 연산을 실행하면 된다. $x=3$인 경우를 생각해 보면 \(11_{(2)} \rightarrow 100_{(2)} \rightarrow 1000_{(2)} \rightarrow 10000_{(2)} \rightarrow \dots\) 으로 차례로 업데이트한다. 즉, 2진수로 봤을 때 최대 $N$자리까지 업데이트 하므로 최대 $O(\log{N})$이 소요됨을 알 수 있다.
저장공간의 경우, 2진수로 표현했을 때 나타나는 사이클을 이용한 자료구조기 때문에 인덱스가 1부터 시작해야 하므로 $N+1$만큼의 크기의 배열이 필요하다. Segment tree보다 적은 공간을 필요로 한다.
시간복잡도의 경우, Segment tree와 동일하게 쿼리 및 업데이트 연산에 $O(\log{N})$만큼의 비용이 든다. 따라서 Fenwick tree를 이용하면 원소 하나씩 업데이트가 되는 상황에서 모든 쿼리를 $O((N+Q)\log{N})$만에 처리한다.
비교
다음은 앞서 소개한 세가지 방법을 비교한 표다.
| Query | Update | Space | Complexity of Implementation | |
|---|---|---|---|---|
| Prefix Sum Array | $O(1)$ | $O(N)$ | $N$ | Low |
| Segment tree | $O(\log{N})$ | $O(\log{N})$ | $4N$ | High |
| Fenwick tree | $O(\log{N})$ | $O(\log{N})$ | $N+1$ | Low |
위의 표만 봤을 때에는 Fenwick tree만 사용할 것 같지만, Segment tree의 경우 응용을 상당히 다양하게 할 수 있기 때문에 Fenwick tree보다 많이 쓰인다.
한계
지금까지 소개한 방법은 다음과 같은 한계를 가지고 있다.
- Range update (구간 업데이트)를 수행하지 못함
- 주어진 배열이 Sparse한 경우 비효율적임
이러한 한계를 극복할 수 있는 방법은 2편에서 소개하도록 하겠다.