Mo’s Algoritm은 수많은 구간 쿼리를 오프라인으로 매우 효율적으로 처리하기 위한 알고리즘이다. 쿼리를 특정 순서로 정렬하여 이전 쿼리의 계산 결과를 최대한 재활용한다.
Mo's Algoritm의 핵심은 두 개의 포인터의 총 이동거리를 최소화하는것이다. 이는 구간의 원소를 효율적으로 추가하고 제거하는 방식으로 동작한다.
현재 $[L, R]$ 구간에 대한 답을 알고 있다고 가정하면 다음 쿼리인 $[L', R']$ 구간의 답을 구하기 위해 $L→L', R→ R'$ 로 포인터를 한칸씩 옮기게 된다. 이때 원소를 추가하거나 제거하면서 결과를 업데이트한다:
예를 들어 다음과 같은 배열이 있다.
만약 이 같은 배열에서 1~4까지의 합을 알고 있고 0~5까지의 합이 필요하다면 좌우로 포인터를 한칸씩 옮기는것으로 전체 합이 구해진다. 왼쪽 포인터를 1→0으로 이동하면서 값 5을 추가하고, 오른쪽 포인터를 4→5로 이동하면서 값 2를 추가한다.
여기까지만 보면 그냥 평범한 투포인터이다. 문제는 쿼리의 범위가 중구난방이면 오히려 포인터가 양 끝을 계속 왕복하여 총 이동거리가 매우 커진다는 점이다. 이렇게 되면 원소의 추가/제거 연산이 비효율적으로 너무 많이 발생한다.
Mo's Algoritm은 이 쿼리를 적절히 정렬하여 이 이동거리를 줄임으로써 원소의 추가/제거 연산을 최소화한다.
가장 처음에는 쿼리가 주어진 순서 그대로 처리된다.