Mo's Algorithm
Mo's Algorithm은 정적 배열에 대한 여러 구간 쿼리
[L, R]를 오프라인으로 재정렬한 뒤, 이전 쿼리 결과를 재사용해서 처리하는 알고리즘이다. 핵심은 각 쿼리를 처음부터 계산하지 않고, 현재 구간의L,R을 조금씩 움직이며 결과를 갱신하는 것이다.
1. 문제 상황
배열 arr와 여러 개의 구간 쿼리가 있다고 하자.
arr = [1, 1, 2, 1, 3, 4, 5, 2, 8]
queries:
[0, 4]
[1, 3]
[2, 4]각 쿼리에 대해 해당 범위의 합을 구한다.
[0, 4] → 1 + 1 + 2 + 1 + 3 = 8
[1, 3] → 1 + 2 + 1 = 4
[2, 4] → 2 + 1 + 3 = 6단순하게 매 쿼리마다 [L, R]을 순회하면 최악의 경우
O(N × Q)가 필요하다.
2. 핵심 아이디어
예를 들어 이전 쿼리가
[0, 4]이고 다음 쿼리가
[1, 4]라면 굳이 [1,4]를 다시 처음부터 계산할 필요가 없다.
sum(0,4) = 8
→ arr[0] 제거
sum(1,4) = 8 - arr[0]
= 7즉,
현재
[curL, curR]의 답을 가지고 있다가L,R을 움직이면서 원소를 추가/제거한다.
Mo's Algorithm은 쿼리의 순서를 적절히 정렬해서 L, R의 총 이동량을 줄이는 것이 핵심이다.
3. 쿼리 정렬 방법
배열을 대략 √N 크기의 블록으로 나눈다.
blockSize = √N그리고 쿼리 [L, R]를 다음 기준으로 정렬한다.
L / blockSize가 작은 순서- 같은 블록이라면
R이 작은 순서
예를 들어
N = 16
blockSize = 4라면:
Block 0: L = 0 ~ 3
Block 1: L = 4 ~ 7
Block 2: L = 8 ~ 11
Block 3: L = 12 ~ 15쿼리가
[1, 10]
[2, 4]
[7, 8]
[5, 12]
[3, 6]라면 대략
L Block 0
[2,4]
[3,6]
[1,10]
L Block 1
[7,8]
[5,12]처럼 배치된다.
4. 왜 이렇게 정렬하는가?
쿼리를 아무 순서로나 처리하면
[0, 100]
→ [900, 950]
→ [10, 50]
→ [800, 999]처럼 L, R이 배열 전체를 계속 왕복할 수 있다.
반면 Mo's ordering을 사용하면 같은 L 블록 안에서는 L의 변화량이 작고, R이 증가하는 순서로 처리되므로 포인터의 총 이동량이 크게 줄어든다. R의 총 이동은 O(N√N), L의 총 이동은 O(Q√N)
5. 실제 처리
현재 처리 중인 구간을
[curL, curR]라고 하자.
새 쿼리
[L, R]가 들어오면 포인터를 맞춘다.
while (curL > L)
Add(--curL);
while (curR < R)
Add(++curR);
while (curL < L)
Remove(curL++);
while (curR > R)
Remove(curR--);결국
[curL, curR]
↓
[L, R]가 될 때까지 경계를 하나씩 이동시키는 방식이다. 현재 합을 유지하면서 경계를 움직일 때 원소를 더하거나 뺀다.
6. 전체 구조
struct Query
{
int l;
int r;
int idx;
};
int blockSize;
sort(queries.begin(), queries.end(),
[](const Query& a, const Query& b)
{
int blockA = a.l / blockSize;
int blockB = b.l / blockSize;
if (blockA != blockB)
return blockA < blockB;
return a.r < b.r;
});이후
int curL = 0;
int curR = -1;
for (Query& q : queries)
{
while (curL > q.l)
Add(--curL);
while (curR < q.r)
Add(++curR);
while (curL < q.l)
Remove(curL++);
while (curR > q.r)
Remove(curR--);
answer[q.idx] = GetAnswer();
}처럼 처리하면 된다.
idx를 저장하는 이유는 Mo's Algorithm이 쿼리 순서를 바꾸기 때문이다. 원래 입력 순서대로 답을 출력하려면 각 쿼리의 원래 인덱스를 기억해야 한다.
7. 시간 복잡도
쿼리 정렬:
O(Q log Q)
쿼리 처리:
O((N + Q)√N)
전체:
O((N + Q)√N)보통 Q ≈ N이라면
O(N√N)정도로 생각할 수 있다.
단, 이는 Add()와 Remove()가 O(1) 정도에 수행된다는 가정이 중요하다.
8. Mo's Algorithm이 적합한 문제
Mo's Algorithm은 특히 다음 조건에서 유용하다.
① 모든 쿼리를 미리 알고 있음
Query 1
Query 2
Query 3
...을 먼저 받은 뒤 순서를 바꿔서 처리한다.
즉 Offline Query Algorithm이다.
② 배열이 거의 변하지 않음
기본 Mo's Algorithm은
Update
Query
Update
Query처럼 배열 수정이 섞이는 문제에는 적합하지 않다.
③ 원소 하나 추가/삭제로 답을 쉽게 갱신 가능
예를 들어:
구간 합
서로 다른 숫자의 개수
각 값의 등장 횟수
frequency 기반 계산등이다.
9. 핵심 정리
Mo's Algorithm
↓
여러 Range Query를 빠르게 처리하는 Offline Algorithm
1. 배열을 √N 크기의 Block으로 나눈다.
2. Query [L,R] 정렬
1순위: L / √N
2순위: R
3. 현재 구간 [curL, curR]을 유지한다.
4. 다음 Query로 이동하면서
L ← → R
Add / Remove 수행
5. 이전 Query의 계산 결과를 재사용한다.핵심 개념
Mo's Algorithm = 쿼리 순서를 바꿔서
L,R포인터의 총 이동량을 최소화하는 알고리즘
복잡도는 일반적으로
O((N + Q)√N)이고, 정적 배열 + 많은 구간 쿼리 + Add/Remove가 저렴한 문제에서 특히 유용
