Mo's Algorithm

Mo's Algorithm

오프라인 범위 쿼리 문제에서 쿼리 순서를 재배치하여 O((n+q)√n) 시간에 처리하는 알고리즘으로, 구간을 √n 크기 블록으로 나누고 블록과 끝점을 기준으로 정렬하여 포인터 이동을 최소화

목적: 범위 쿼리 최적화, 오프라인 쿼리, 구간 문제 해결

특징: 오프라인(모든 쿼리 미리 알아야 함), 블록 분할, 정렬 기반, 포인터 이동 최소화

핵심 아이디어: 쿼리 순서를 재배치하여 구간 [L, R] 변화를 최소화 → 포인터 이동 최소화

쿼리 정렬: ① L을 블록 번호(L/√n)로 정렬 ② 블록 같으면 R로 정렬 (블록 번호 홀수면 R 내림차순)

동작: ① 쿼리 정렬 → ② 현재 구간 [curL, curR] 유지 → ③ 쿼리 [L, R]로 포인터 이동 → ④ 이동 중 add/remove 연산으로 답 갱신

블록 크기: √n이 최적, 포인터 이동 거리와 블록 수 균형

시간 복잡도: O((n+q)√n), n = 배열 크기, q = 쿼리 수, 포인터 이동 O(n√n) + 쿼리 정렬 O(q log q)

공간 복잡도: O(n + q)

장점: 간단한 구현, 범위 쿼리 최적화, 다양한 문제 적용

단점: 오프라인만 가능, √n 복잡도, add/remove 연산 필요

적용사례: 구간 내 서로 다른 원소 수, 구간 내 원소 빈도, 구간 XOR, 구간 GCD

비교: Mo's(오프라인/√n) vs 세그먼트 트리(온라인/log n) vs Sqrt Decomposition(온라인/√n)

연관: 범위 쿼리, 오프라인 알고리즘, Sqrt Decomposition, 블록 분할