HilbertMO : alternative query sorting for Mo's algorithm

원본 Codeforces 블로그

문제를 잘 푸는 사람일수록 알고리즘을 암기하기보단 끊임없이 고찰하고, 최적화하고, 예외를 효과적으로 비껴가는 방법을 연구하는 것 같다. 그런 의미에서 이 포스팅 작성자도 굉장히 존경스럽다. 세상은 넓고 갓갓은 많아..

---

MO's algorithm

흔히 루트질로 불리는 MO's algorithm은 배열에 대한 구간 쿼리를 오프라인으로 처리하는 많은 문제를 아슬아슬한 복잡도로 해결할 수 있게 해주는 트릭이다.

kesakiyo님의 친절한 introduction

끄흐수님의 깔끔한 introduction

MO's algorithm으로 문제를 풀기 위해서는 다음이 성립해야 한다 : 

- 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s-1, e] 또는 [s, e+1]에 대한 답을 빠르게 알 수 있다. (push)

- 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s+1, e] 또는 [s, e-1]에 대한 답을 빠르게 알 수 있다. (pop)

: push / pop을 쿼리 옮기기라고 하자.

저 조건이 주어졌을 때 바로 떠오르는 Naive한 알고리즘이 있다.

- 쿼리를 아무 생각 없이 죽 늘어놓고, \(i\)번째 쿼리 \([s_{i}, e_{i}]\)에서 \(i+1\)번째 쿼리 \([s_{i+1}, e_{i+1}]\)로 넘어갈 때 쿼리 옮기기를 \(|s_{i} - s_{i+1}| + |e_{i} - e_{i+1}|\) 번 사용해서 넘어간다.

하지만 이 알고리즘은 \((s_{2i}, e_{2i}) = (1,1)\), \((s_{2i-1}, e_{2i-1}) = (n, n)\)으로 주어질 경우 쿼리 옮기기에 \(\Theta (N)\)의 시간이 소모되므로 얄짤없이 \(O(QN)\)이 된다.

Mo's algorithm의 경우 이 쿼리 옮기기가 적어지도록 쿼리를 잘 정렬하자는 아이디어에서 출발한다.

길이 \(B\)인 bucket으로 배열을 분할하자. 그리고 \(Q\)개의 쿼리를 다음의 comparator function으로 정렬한다.

두 쿼리 \([s_{1},e_{1}],[s_{2},e_{2}]\)를 정렬한다고 하자. 

- \(s_{1}\)과 \(s_{2}\)가 속한 bucket 번호가 같다면, \(e\)가 작은 쪽이 더 작다.

- 그렇지 않다면 bucket 번호가 작은 쪽이 더 작다.

이와 같이 정렬하고 위의 Naive 알고리즘을 적용하면 쿼리 옮기기의 횟수는 \(O(QB + \frac{N^2}{B})\)가 된다!

이유를 설명하려고 했지만 위의 블로그에 더 잘 쓰여 있기도 하고, 본론과는 거리가 머니 넘어가자.

증명을 직접하는 것도 나쁘지 않다. 쿼리를 bucket 안에서 움직일 때와, 다른 bucket으로 넘어갈 때로 나눠 생각해보자.

따라서 \(B = \sqrt{N}\)으로 잡으면 \(O\left((N+Q)\sqrt{N}\right)\)이고, 치졸하게 \(B = \frac{N}{\sqrt{Q}}\)로 잡으면 이론상 최적인 \(O(N\sqrt{Q})\)가 나온다. 물론 practical한 차이는 보이지 않고 코딩만 까다로워지니 착한 어린이들은 \(\sqrt{N}\)으로 잡자. 예외가 싫다면 \(\sqrt{N + 1}\)도 나쁘지 않다.

---

Hilbert MO : TSP와의 연관성

HilbertMO를 떠올릴 수 있는 가장 중요한 관찰은, 쿼리 옮기기를 하나의 TSP로 생각할 수 있다는 점이다!

쿼리로 주어지는 \([s_{i}, e_{i}]\)를 2D plane의 한 점으로 생각해보자. 그럼 1번의 쿼리 옮기기 횟수는 두 점의 맨해튼 거리(택시거리) 로 주어진다. 총 \(Q-1\)번의 쿼리 옮기기를 최소비용으로 수행한다는 것은 결국 맨해튼 거리공간에서의 Hamiltonian path를 찾는 문제와 동치가 된다!

이렇게 생각했을 때, bucket을 사용한 Mo's algorithm은 다음의 그림으로 표현할 수 있다. x좌표는 \(s\), y좌표는 \(e\)다. \(y \ge x\)가 성립해야 함에 주목하자.

그런데, 이런 Manhattan TSP에서는 space - filling curve를 이용한 점 sorting이 좋은 heuristic으로 알려져 있다.

그래서 여기에 space - filling curve인 Hilbert Curve를 가져온다! 

\(2^k \times 2^k\) board 위에 Hilbert Curve를 그린다고 하자. \((2^k \ge N)\)

이 때 이 Curve가 점 \((x,y)\)를 몇 번째로 방문하는지는 \(O( \lg N )\)만에 알 수 있다. 이 때 이 방문 순서를 기준으로 점들을 정렬한다.

이 경우 쿼리 옮기기의 횟수는 \(O(N \sqrt{Q})\)가 된다.

편의상 \(N = 2^{k}, Q = 4^{l}\)이라고 둔다. Naïve Mo의 bound 증명 과정과 크게 다르지 않음에 주목하자. \(2^l = \sqrt{Q}\)이다.

Hilbert Curve는 recursive하다. 즉, Level \(i\)의 Hilbert Curve를 4개의 영역으로 나누면, 각각의 영역에는 (회전된) 4개의 Level \(i - 1\) Hilbert Curve가 그려져 있다는 것이다.

따라서 Level \(k\)의 Hilbert Curve를 \(2^{k-l} \times 2^{k-l}\)의 정사각형 영역들로 나누자. 이때 각각의 영역은 Level \(k - l\)의 Hilbert Curve를 포함하며, 커다란 영역들은 Level \(l\)의 Hilbert Curve를 이룬다.

Case 1. 영역이 바뀌는 쿼리

영역을 바꿔야 하는 횟수는 총 \(4^{l} - 1\)번이며, 한 번의 영역 전이는 아무리 커봐야 한 정사각형의 길이 =  \(2^{k-l}\)번의 쿼리 옮기기로 만들 수 있으므로 이 경우 필요한 쿼리 옮기기의 횟수는 \(O(2^{k+l} = N \sqrt{Q})\)이다.

Case 2. 한 영역 내부의 쿼리.

한 영역 내부에 있는 두 점의 거리는 길어봐야 \(2 \times 2^{k-l}\) 정도이다. 따라서 필요한 쿼리 옮기기의 횟수는 \(O(q \times 2^{k-l} = N \sqrt{Q})\)가 된다.

---

Practical Performance

상세한 벤치마킹 결과는 원본 링크에서 확인할 수 있다. 

랜덤 데이터에서의 경향성을 보자면, 대부분의 경우 Classic Mo's algorithm을 압도하는 performance를 보여주고 있다.

여담이지만 \(N\)이 크고 \(Q\)가 작은 경우의 압도적 performance 차이는 함정이다. 이 경우 \(B = \frac{N}{\sqrt{Q}}\)로 잡으면 큰 차이가 나지 않는다. 물론 그래도 Hilbert MO가 더 빠르다 ^^

실제로 BOJ 13545 - 수열과 쿼리 0을 이용해 벤치마킹한 결과 \(O(N\sqrt{Q}\lg N)\)짜리 풀이에서 1.4 ~ 1.7배의 성능 차이를 보인다.

주) 원래 저 문제는 저렇게 쌩 Mo질로 풀라고 만든 문제는 아니다. hilbertMO가 빠르다는 사실만 참조하자...