Mo's Algorithm
21 Jun 2021변하지 않는 수열이 있다고 할 때 쿼리가 엄청나게 많이 들어온다고 하자. 이 때 각각의 쿼리마다 새롭게 모든 것을 구해주면 굉장히 시간이 오래걸릴 것이다. 만약 쿼리들을 어떤 순서로 정렬해서 이전 결과를 다음 결과에 활용할 수 있다면 시간 단축에 큰 도움이 될 것이다. 이런 방식으로 시작하는게 바로 mo’s algorithm이다.
위의 그림을 보자. 4-6, 3-8, 3-5 구간을 구하는 쿼리가 들어온다고하자. 그렇게되면 그림처럼 4-6 쿼리에서 3-8 쿼리로 갈때는 왼쪽을 한칸 오른쪽을 2칸 이동시키면 결과를 구할 수 있다. 마찬가지로 3-5 구간도 오른쪽을 세칸 감소시키면 이전 결과에서 새로운 결과를 얻어낼 수 있다. 이처럼 이전 쿼리의 결과를 활용하여 새로운 쿼리를 구하는 방법을 mo’s algorithm이라고 부른다.
그렇다면 어떤 규칙으로 정렬을 시켜야할까? 바로 시작 지점에 대해 평방 분할을 사용해서 정렬하면 된다. 평방 분할이란 주어진 구간을 sqrt(n)으로 나누어 관리를 하는 것이다.
그림의 색깔이 다른 부분은 서로 다른 평방 영역에 해당하게 된다. 이렇게 평방 분할을 하면 뭐가 좋을까? 쿼리들을 두개의 조건으로 정렬한다고 하자.
1) Q[i].e < Q[i+1].e
2) Q[i].s / sqrt(n) < Q[i+1] / sqrt(n)
평방 영역이 같을 경우 내부에서 구간을 이동시켜봤자 최대 sqrt(n)밖에 되지 않는다. 총 n개에 대해서 실시하므로 O(n sqrt(n)) 의 시간이 걸리게 된다. e의 이동은 증가하도록 정렬했기 때문에 최대 n밖에 이동하지 않는다.
평방 영역이 다를 경우 구간 이동을 최대 n하게 된다. 하지만 구간 자체가 sqrt(n)개로 쪼개졌기 때문에 다른 평방으로의 구간이동을 하는 횟수는 전체 통틀어서 sqrt(n)이다. 따라서 전체 걸리는 시간은 O(n sqrt(n)) 의 시간이 걸리게 된다.