---
id: "imported/ps/algorithm/general/mo"
title: "Mo's"
description: "개인적으로 공부하다가 그 심플함과 발상에 충격먹은 알고리즘 1순위 (2023/07 기준)"
kind: "record"
published: "2023-10-29T00:00:00.000Z"
tags: ["mo's","offline query"]
url: "https://www.readiz.com/notes/algorithm/general/mo/"
markdownUrl: "https://www.readiz.com/notes/algorithm/general/mo/index.md"
---
# Mo's
개인적으로 공부하다가 그 심플함과 발상에 충격먹은 알고리즘 1순위 (2023/07 기준)
`Mo's Algorithm`을 내가 이해한 순서대로 한번 정리해보고자 한다.
## TL;DR
Offline Query가 가능해야 함, 아래와 같이 쿼리 정렬
- $sqrtN = \sqrt N$
```cpp
struct Q { // Query
int s, e;
int oidx; // Original Index
bool operator<(const struct Q& t) const {
if (e / sqrtN == t.e / sqrtN) return s < t.s;
return e / sqrtN < t.e / sqrtN;
}
};
```
## Bucket Challenge
난 개인적으로 `bucket`을 활용한 풀이를 매우 좋아한다. 알고리즘 명으로는 `Sqrt Decomposition`으로 많이 부르는 기법인데, 전체 배열 크기가 $N$ 일때, 전체 구간을 $\sqrt N$ 으로 나누게 되면, 각 `bucket`의 크기 또한 $\sqrt N$이 된다. 이렇게 되면, 각 구간마다의 계산값(이를테면 구간마다의 합)을 구하는 데에 최대 $O(\sqrt N)$의 시간이 걸리게 되는 아름다운 결론에 도달한다.
예를 들어, 전체 구간 크기가 `10000`이면, 각 구간은 `100`으로 나눌 수 있고, 이 상태에서 각 구간의 합을 `bucket[i/100]`에 미리 계산해 두었다고 하자. 그러면, $[4, 303]$ 구간의 합은 미리 계산해둔 값들을 바탕으로 아래처럼 구하면 된다.
- A\[4], A\[5], A\[6], ... A\[99]
- bucket\[1] (100 \~ 199의 합이 미리 계산되어 있다)
- bucket\[2] (200 \~ 299의 합이 미리 계산되어 있다)
- A\[300], A\[301], ... A\[303]
위에서 확인이 가능한 것처럼, bucket 외의 구간을 합해야 하는 수는 worst의 경우에도 $\sqrt N$을 넘지 않는다. 따라서 이런 경우 `query` 마다의 시간 복잡도는 최대 $O(\sqrt N)$이 된다고 할 수 있는 것이다.
## Mo's Algorithm
바로 이러한 루트로 나누는 아이디어를 `Offline query`에 적용한 것이 `Mo's Algorithm`이다. `Offline query` 역시 발상이 독특한데, `query`를 꼭 입력이 들어온 순서대로 처리하지 않는 것을 말한다. 만약 아래와 같은 `query`가 반복된다고 해보자.
- $[1, 100]$
- $[1000, 1300]$
- $[2, 101]$
- $[1001, 1301]$
- $[3, 102]$
- $[1002, 1302]$
딱 봐도 `query`를 재배치하고 싶은 욕구가 생길 것이다. 재배치하면 이전에 계산한 값을 활용할 여지가 있기 때문이다. 다만, 재배치를 `일반적으로` 어떤 순서로 할 것인지가 막막하다. `Sqrt Decomposition`까지는 루트를 어떻게 활용할지에 대한 아이디어가 어느 정도 직관으로 찾아지지만, `Mo's` 정도 되면 쉽지 않다. 재배치 방식에 대해 아래처럼 생각을 해보는 것이 일반적일 것이다.
1. $[s, e]$에 대해서 `s` 먼저 정렬하면?
- $[1, 100]$, $[1, 10000]$, $[2, 100]$, $[2, 10000]$ 처럼 질의가 올 수 있다.
2. $[s, e]$에 대해서 `e` 먼저 정렬하면?
- 1과 같은 반례가 존재한다.
3. $[s, e]$에 대해서 `s` 먼저 정렬하고 같으면 `e`로 정렬하면?
- 그럴싸 하지만, 전체적으로 비효율이 존재하는 것은 마찬가지이다.
- 아래 케이스가 여전히 해결이 안된다.
- $[1, 2]$, $[1, 10000]$, $[2, 3]$, $[2, 10001]$, ...
즉, 위처럼 단순 정렬 해서는 어떻게 정렬해도 쉽지 않다. `Mo's Algorithm`은 엄청난 발상에서 출발하는데, 바로 한쪽 구간에 루트를 취하는 것이다. 아래와 같은 `operator`를 통해 정렬하는 것을 생각해보자.
```cpp
bool operator<(const struct Q& t) const {
if (e / sqrtN == t.e / sqrtN) return s < t.s;
return e / sqrtN < t.e / sqrtN;
}
```
$\sqrt e$가 같을 때 $s$를 활용해 오름차순으로 하고, 다를 때는 $\sqrt e$가 오름차순으로 정렬하는 것이다. 이렇게 하면, 처음의 예시가 아래처럼 깔끔하게 떨어진다. ($N = 10000$을 가정하자)
- $[1, 100]$ : `e`가 `bucket` 1에 속하므로 제일 먼저 온다.
- $[2, 101]$ : 위와 동일한 `bucket`이고, `s`의 순서에 따라 정렬되었다.
- $[3, 102]$
- $[1000, 1300]$ : `e`가 `bucket` 13에 속하므로 1번보다 나중에 온다.
- $[1001, 1301]$
- $[1002, 1302]$
직관으로 확인해봐도, `query` 간 이동할 때 걸리는 시간이 상당히 개선이 될 것이라고 짐작할 수 있다. `s`와 `e`가 이동하는 전체적인 거리를 생각해보자.
1. `e`는 전체적으로는 $O(N)$, 그리고 `query` 구간 내에서 $O(\sqrt N)$ 만큼 이동 가능하고, `query`수가 $M$개라고 하면, 총 $O(N + M\sqrt N)$ 만큼 이동할 수 있다.
2. `s`는 `e`가 최대 $O(\sqrt N)$ 만큼 이동하는 동안 오름차순 정렬되어 있으므로 최대 $N$만큼 이동가능하다. 즉, 총 $O(N\sqrt N)$ 만큼 이동할 수 있다.
1과 2를 둘 다 고려하면 최종적인 시간 복잡도인 $O((N + M)\sqrt N)$이 나온다.
## Time Complexity
- 구간 길이 N이고, 쿼리 M개 일 때,
- $O((N+M) \sqrt N)$
하나의 `query`를 수행하는 데에 걸리는 시간이 $O(1)$이 걸린다면, 전체적인 시간복잡도는 위에서 살펴본 것처럼 $O((N + M)\sqrt N)$이 된다. `naive`하게 전체 `query`를 처리했다면 $O(NM)$이 걸렸을 것이므로, 엄청난 개선이 된다고 할 수 있다.
### 참고 링크
- 소멤블로그 `Mo's Algorithm` 소개:
- 백준 `수열과 쿼리 5`: