Mo’s Algorithm

개요

Mo’s Algorithm은 범위 쿼리(range query)를 다수 처리해야 하는 상황에서 전체 쿼리를 오프라인으로 정렬한 후 슬라이딩 윈도우 기법을 이용해 효율적으로 처리하는 알고리즘입니다. 주로 수열에서의 구간 합, distinct 수, 빈도 등 다양한 누적 정보 질의 문제에 사용되며, 쿼리 수가 많고 온라인 처리가 불가능할 때 유용합니다. 쿼리 순서를 정렬하여 윈도우 이동량을 줄이는 것이 핵심 전략입니다.

---

1. 개념 및 정의

항목	설명
정의	Mo’s Algorithm은 쿼리들을 sqrt(n) 블록 단위로 정렬한 후, 슬라이딩 윈도우로 범위 연산을 최적화하는 오프라인 쿼리 처리 알고리즘입니다.
목적	범위 쿼리 문제에서 쿼리 이동량을 줄여 성능 향상
필요성	쿼리 수(Q)가 많고, 데이터 크기(N)에 따라 naive한 반복 처리 방식은 비효율적

Mo’s Algorithm은 시간 복잡도를 O((N + Q) * √N) 수준으로 낮출 수 있습니다.

---

2. 핵심 원리 및 절차

단계	설명	주요 연산
쿼리 정렬	왼쪽 인덱스를 √N 블록 기준으로 정렬하되, 오른쪽 인덱스로 tie-break	O(Q log Q) 정렬
윈도우 확장/축소	현재 쿼리 범위에 따라 윈도우 좌우 포인터 조절	add/remove 연산 수행
누적 정보 업데이트	쿼리 결과를 위한 상태 변수 갱신	카운터, 배열, 맵 등을 이용
결과 저장 및 출력	쿼리 순서에 맞춰 답 기록	오프라인이므로 쿼리 인덱스 유지 필요

Mo’s Algorithm의 성능은 add(i), remove(i)의 시간 복잡도에 따라 달라집니다.

---

3. 시간 복잡도 분석

항목	설명
정렬	O(Q log Q)
각 쿼리당 add/remove	평균적으로 O(√N) 이동
총 수행 시간	O((N + Q) * √N) (add/remove 비용이 O(1)일 때)
공간 복잡도	O(N + Q) (count 배열, 결과 저장용 등)

Mo’s Algorithm은 Q가 많을수록, 그리고 online 쿼리보다 offline 정렬이 가능할수록 효과적입니다.

---

4. 사용 예시 및 확장

유형	문제 예시	고려사항
수열에서의 distinct 수	구간 [l, r]에 서로 다른 숫자 개수	카운터 배열 활용
특정 수 빈도 구간 질의	구간 [l, r]에서 수 x의 등장 횟수	맵 또는 frequency 배열 사용
구간의 XOR/AND/OR 등	구간의 XOR 합	연산 성질상 add/remove 구현 필수
시간에 따른 변경 포함 (Extended Mo)	쿼리 중간에 수열 변경 포함	변경 기록과 rollback 처리 필요

Mo의 확장은 변경 쿼리 포함(시간 블록 정렬), 이차원 적용(행렬 슬라이딩) 등 다양하게 가능.

---

5. 구현 팁

항목	팁
쿼리 정렬 기준	왼쪽 블록 번호 정렬 후, 오른쪽 인덱스는 지그재그 정렬 (짝수는 오름차순, 홀수는 내림차순)
인덱스 0 기반 처리	add/remove 시 경계 조건 주의
쿼리 인덱스 유지	오프라인 결과 저장 시 original_index 필수
시간 제한 주의	쿼리 수가 10⁵ 이상일 경우 최적화된 add/remove 필요
STL 활용	C++의 map, vector, deque 등 유용

효율적인 구현을 위해 입출력 속도 개선(fast IO), 캐싱 최적화도 병행 필요.

---

6. 장점과 한계

장점	설명
빠른 쿼리 응답	반복 계산 제거로 성능 향상
쉬운 확장성	다양한 누적 연산에 맞게 응용 가능
경량화된 구조	트리 구조, 세그트리보다 가볍고 구현 간단

한계	설명
온라인 쿼리 불가	모든 쿼리를 미리 알고 있어야 함
실시간 대응 불가	쿼리 도중 상태 변화가 있으면 적용 어려움
add/remove 구현 필요	연산 로직이 단순하지 않으면 어렵다

---

7. 결론

Mo’s Algorithm은 수많은 오프라인 쿼리를 빠르게 처리해야 하는 상황에서 매우 효과적인 알고리즘입니다. 슬라이딩 윈도우와 블록 정렬이라는 간단한 아이디어를 바탕으로, 복잡한 자료구조 없이도 경로 질의 문제를 효율적으로 해결할 수 있습니다. 특히 알고리즘 대회나 실용적인 로그 분석, 범위 빈도 통계 등에 유용하며, 알고리즘 학습자에게는 쪼갬과 정렬의 조합으로 최적화를 달성하는 좋은 예시가 됩니다.