알고리즘, 그 첫 번째 이야기 | Sqrt Decomposition

sqrt decomposition은 주로 연속한 원소를 하나로 묶어서 처리하며, 시간복잡도에 특이하게도 $\sqrt N$이 들어간다. 

아이디어는 간단하다. 예를 들어 다음과 같은 문제를 푼다고 가정하자.

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

이 문제는 길이 N의 input 배열에서 다음과 같은 것을 Q번 처리하면 된다.

1. input[b]의 값을 c로 바꾼다.

2. [b,c] 구간에 있는 수들의 합을 구한다.

만약 1번이나 2번만 있다면 1번은 당연히 $O(Q)$로 가능하고 2번은 S[0]=input[0],S[i]=S[i-1]+input[i]로 정의하면 각 쿼리를 S[c]-S[b-1]로 풀 수 있으므로 S를 계산하는데 $O(N)$, 쿼리를 처리하는 데 $O(Q)$가 걸리므로 총 $O(Q+N)$에 풀 수 있다. 이 배열을 prefix sum이라고 한다. 하지만 두 개가 모두 있을 경우 prefix sum에서 1번을 처리할 때 [b,N]의 범위에 있는 모든 수를 바꾸어주어야 하므로 시간복잡도가 $O(QN)$이 되어버린다. 그렇다면 다음과 같이 생각해 보면 어떨까? K개의 연속한 원소를 묶어서 그것을 그 원소들의 합을 가지는 하나의 집합으로 생각해 보자.

이 그림에서 N=9, K=3이다.

이렇게 하면 1,2번을 다음과 같이 처리할 수 있게 된다.

1번 : 예를들어 5번 원소의 값을 3으로 바꾼다고 가정하자. 그러면 그 원소가 속한 집합의 합을 다시 계산해준다.

이 때 걸리는 시간은 O(K)이다.

2번 : 예를 들어 [2,7] 구간의 합을 구한다고 가정하자.

이 때 더할 구간의 범위에 그룹 전체가 들어가 있으면 원소 각각을 더하는 대신 미리 구해놓은 합을 쓸 수 있다.

그룹 전체가 들어가 있지 않으면 원소 하나하나를 더한다. 

당연히 원소 하나하나를 더하는 행위는 최대 2K번만 일어나고, 그룹을 더하는 것은 최대 N/K번 일어나 시간복잡도로 쓰면 $O(K+N/K)$로 쓸 수 있다.

따라서 총 시간복잡도는 $O(Q(K+N/K))$가 된다. 따라서 시간복잡도를 줄이려면 K+N/K의 값을 최소화하는 K를 찾으면 되는데, $K = \sqrt N$일 때 이 시간복잡도가 최소가 됨이 알려져 있다. 따라서 K를 저렇게 정의하면 시간복잡도 $O(Q\sqrt N)$으로 풀 수 있게 된다.

이때 크기 K의 집합을 버킷이라고 한다.

이런 식으로 버킷을 만들면 풀 수 있는 문제들이 있다. 예시로는

https://www.acmicpc.net/problem/5823

5823번: 코끼리

https://www.acmicpc.net/problem/17711

17711번: Sushi

등이 있다.