구간의 합 구하기

$N$개의 숫자가 늘어서 있다.
이중 몇 번째부터 몇 번째까지의 숫자들의 합을 물어보는 질문이 여러 번 주어진다.

이것이 구간의 합 구하기(range sum query) 문제의 가장 기본적인 내용이다.
우리의 목적은 아무 구간이나 잡았을 때 그 합을 빠르게 계산하는 것이다.
그 계산이 빨라야 제한 시간 내에 충분히 여러 번 물어볼 수 있기 때문이다.

단순히 고정된 값들에 대해서 구간의 합을 계산하는 거라면, prefix sum 기법을 먼저 떠올릴 수 있다.

2013/07/29 - [알고리즘 문제풀기/# 기타 주제] - Prefix sum

prefix sum 기법은 고정된 값들에 대해서, $O(N)$ 시간이 드는 전처리(=자료 준비)를 한 번 거치면,
이후 모든 구간에 대한 질문을 $O(1)$에 즉각 처리할 수 있다.

그런데 각 요소가 도중에 변할 수 있다면...?
여기부터는 완전히 새로운 발상이 필요하게 되는데, 그 이유를 알아보자.

prefix sum 기법에서는 첫 번째부터 $i$번째까지의 값의 합을 한 번 구해 놓고, 그 값을 계속 사용하게 되는데,
도중에 만약 $i$번째 위치의 값에 갱신이 필요하다면,
prefix sum 배열에서는 $i$번째, $(i+1)$번째, $(i+2)$번째, ... 이 위치들의 값을 변화시켜 주어야 한다.
$i$번째 위치의 값을 가지고 있는 것은 $i$번째 이후의 prefix sum 값들이기 때문이다.

그러면 앞쪽 요소에 갱신이 무지막지하게 많이 들어오면 매번 배열 전체를 돌면서 prefix sum을 갱신해 주어야 한다.
배열의 크기가 $N$일 때, 처음에 $O(N)$의 시간을 소요해서 prefix sum 배열을 만들면
이후 구간의 합 질문을 $O(1)$에 처리할 수 있는게 prefix sum의 장점이었는데,
값 수정을 처리하기 위해서는 최악의 경우 배열 전체를 다 돌아야 하기 때문에 $O(N)$이라고 말할 수 있다.

구간의 합 질문과 특정 위치의 값 수정이 막 섞여서 들어온다면 결국 하나의 질문을 $O(N)$에 처리하게 되는 셈이다.
...그러면 차라리 구간의 합을 구할 때, 해당 구간을 일일이 돌면서 직접 손수 합을 계산하는 것과 차이가 없다.
그것 역시 구간 길이에 비례하는 시간이 들기에 $O(N)$이기 때문이다.

여기서 우리는 "구간의 합 질문과 특정 위치의 값 수정이 막 섞여서 들어올 때"의, 최악의 시간복잡도를 어떻게든 줄이는 것이 목적이다.

위에서 일어난 트레이드오프 trade-off를 고민해보자.

어떤 구간의 합을 미리 계산해서 정리해 놓으면, 궁금한 구간이 있을때 미리 계산한 자료를 이용해 빠르게 답을 구할 수 있다.
이걸 아예 안 한다면, 질문이 들어올 때 질문 구간의 원소 하나하나를 돌면서 합해야 한다.
약간만 한다면..? 예를 들어 인접한 원소 두 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/2 개의 값을 합하면 된다.
미리 계산해놓은 것이 많으면 많을 수록, 질문에 대답하기 위해 합쳐야 하는 갯수는 줄어드는 것이다.

하지만 그렇게 계산해놓은 구간들이 너무 많고, 별로 좋지 않은 모양을 하고 있으면 갱신할 때 오래 걸릴 수 있다.
핵심은, 한 원소를 갱신을 할 때는 그 원소를 포함하고 있는 모든 구간(prefix sum에서는 $i$번째 이후의 모든 합들)을 갱신해주어야 하고,
그게 너무 많으면 그만큼 오래 걸리는 것이다.

이 두 가지 문제를 정리해보면, 우리에게 필요한 것은 다음과 같다.
1) 임의의 구간에 대한 질문이 들어오더라도, 미리 계산해놓은 자료 몇 개의 합으로 표현할 수 있어야 한다. 그 갯수는 충분히 작아야 한다.
2) 임의의 위치에 대한 수정이 들어오더라도, 미리 계산해놓은 자료 몇 개만 바꿔야 한다. 그 갯수는 충분히 작아야 한다.
이 두 가지 조건을 만족하는 여러 자료구조가 있다.

1. Fenwick tree

2. segment tree

이것들은 별도로 글을 써서 올려야겠다.

3. 버킷 (속어로는 "루트질")

위에서 말했듯이,

인접한 원소 두 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/2 개의 값을 합하면 된다.
인접한 원소 네 개씩의 합 까지만 미리 계산해 놓는다면, 약 (구간의 길이)/4 개의 값을 합하면 된다.
....
뭐지? 인접하게 여러 개를 묶으면 다 되는 건가?

아니다. 예를 들어 10,000개의 값이 있고, 인접한 1,000개의 합을 미리 계산해 놓았다고 하면,
적당히 큰 구간이 들어왔을 때 많아야 열 개의 값(질문으로 들어온 구간에 완전히 포함되는 덩어리)을 합하면 될 것처럼 보이지만,
거기에 포함되지 않은 양쪽 가장자리도 있기 때문에 최악의 경우에는 999×2 번의 덧셈이 더 필요하다.

$t$개씩 한 덩어리로 묶어서 미리 합을 계산해 놓는다고 했을 때 시간을 계산해보자.
(여기서 각각의 덩어리들이 안 겹치게 잡았다고 하자. 즉 $1$번째부터 $t$번째까지, $(t+1)$번째부터 $2t$번째까지, ... 이런 식이다.)

구간에 포함되는 덩어리가 $\left \lfloor{N/t}\right \rfloor$개, 양쪽에 남는 원소가 최대 $2(t-1)$개이므로
매 질문에 대해서$O(\max \{N/t, t\})$에 대답할 수 있다.
특정 위치의 갱신은 그 값과 그것을 포함하는 덩어리 두 개의 값만 바꿔주면 되므로 $O(1)$이다.

이때 $t=\sqrt N$으로 잡으면, 매 질문에 대해서 $O(\sqrt{N})$에 대답할 수 있는 훌륭한 자료구조가 완성되었다.
물론 $t=2\sqrt N$이나, $t=0.125 \sqrt N$으로 잡아도 시간복잡도는 동일하기는 하나, 실제로 구현해서 랜덤 데이터를 넣어보면 당연히 소요 시간은 달라진다. 그런 걸 생각하기 어렵기도 하고, 데이터를 모르는 상태에서는 할 수 있는 합리적 추측이 없기 때문에 그냥 $t=\sqrt N$로 많이 쓴다.

이렇게 $\sqrt N$에 비례하게 묶어 미리 저장해둔 덩어리, 혹은 이 기법을 버킷(bucket)이라고 부른다.
버킷을 사용한 풀이는, 추가적인 자료구조나 기타 기법들의 유무에 따라 $O(N \sqrt N)$이나 $O(N \sqrt N \log N)$ 정도의 시간 복잡도를 가지게 되는 것이 일반적이다.

$\sqrt N$이 좀 크지 않냐고 할 수 있는데, 문제를 푸는 데에 있어서 $O(N\sqrt N)$은 $N \leq 100,000$이라면 1초 안에 충분히 돌아가고도 남을 만큼 빠른 방법이다. 경험적으로는 $O(N \log ^2 N)$와 비슷한 시간이 걸린다. $O(N \sqrt N \log N)$ 역시 대부분의 경우에 큰 지장이 없이 문제를 풀 수 있다. 다만 $O(N \sqrt N \log ^2 N)$ 처럼 로그가 한 번 더 붙게 되면, 충분히 빠른 $O(N^2)$과 비슷한 수준이 된다.

어려운 풀이를 요구하는 문제에서, 쉽게 생각 가능한 풀이에 버킷 혹은 $\sqrt N$에 비례하는 무언가를 사용해 시간을 약간 더 빠르게 하면 놀랍게도 생각보다 빨리 작동해 정답을 받는 경우가 종종 있다. 때문에 약간의 비하적인 의미를 담아 이들 기법을 묶어서 '루트질'이라고 부르는 일이 많다.

또한 구현이 생각보다 어려울 수 있어서, 개인적으로는 초보자에게는 별로 추천하지 않는다. 아닌가? 사실 그렇게 어렵지만도 않긴 한데...