[알고리즘] 제곱근 분할법(Sqrt Decomposition)

제곱근 분할법(Sqrt Decomposition)이란?

Sqrt Decompostion 의 아이디어는 다음과 같다.

1 2 3 4 5 6 7 8 9

위와 같이 9 개의 원소가 있다면 연속적인 원소들을 하나의 묶음으로 생각한다는 것이다.

이 때 한 묶음을 √N 개로 묶는다( 따라서 Sqrt 라는 이름이 붙는다.)

(1,2,3),(4,5,6),(7,8,9)

위와 같이 3개의 그룹으로 묶은 다음 각 그룹에 대푯값을 정한다.

만약 그룹의 합을 구하는 쿼리라고 하면 그룹의 합이 대푯값이 되고 쿼리가 구간의 최댓값을 구하는 쿼리라면 그룹의 최댓값이 구간의 쿼리가 된다.

이러한 제곱근 분할법은 Mo's Algorithm 의 기반이 되는 알고리즘으로 사용된다.

 

제곱근 분할법(Sqrt Decomposition) 구현

여기서는 구간의 합을 구하는 문제를 예를 들어 살펴 보자.

6			15			34
1	2	3	4	5	6	7	8	9

구간의 합이라면 위와 같이 각 그룹의 합이 대푯값이 된다.

- 초기화 작업

N개의 데이터를 입력 받으면 √N 개의 원소들로 이루어진 그룹을 만들어야 한다.

long long arr[1000010];
long long group[10010];
int n;
void init(){
	int sq = sqrt(n);
	for(int i=0;i<n;i++) group[i/sq]+=arr[i]; //대푯값을 구한다.
}

- update 구현

만약 위에서 5 위치가 15로 변경이 된다면 그 원소가 속한 그룹에 있는 원소의 합을 구해 대푯값을 갱신해 주면 된다.

여기서 시간은 O( √N ) 의 시간이 걸린다.

6			15			34
1	2	3	4	15	6	7	8	9

void update(int index,long long val){    
    int sq = sqrt(n);
    int groupNum = index / sq; //그룹번호
    int s = groupNum * sq; //그룹의 시작점
    arr[index]=val;
    group[groupNum]=0; //group의 합을 다시 계산
    for(int i=s;i<s+sq;i++) group[groupNum]+=arr[i];
}

- query 구현

위에서 2번째 부터 8번째 까지의 합을 구한다고 하면 두번째 그룹은 대푯값을 그대로 가져 오고 첫번째 그룹의 2번째 ~3번째 까지의 합, 3번째 그룹의 7번째 ~ 8번째 까지의 합을 구해 오면 된다.

long long query(int left,int right){
    long long res = 0;
    int sq = sqrt(n);
    while(left<=right && left % sq) res +=arr[left++]; //왼쪽 그룹의 잔여 갯수의 합
    while(left<=right && (right+1) % sq) res +=arr[right--]; //오른쪽 그룹의 잔여 갯수의 합
	//가운데 그룹 갯수의 합을 구하자.
    while(left<=right){
    	res+=group[left/sq];
        left+=sq;
    }
	return res;
}

백준의 2042번 구간합 구하기 문제( https://www.acmicpc.net/problem/2042 )를 위 알고리즘으로 풀어 보자.

#include <bits/stdc++.h>

using namespace std;
long long arr[2000010];
long long group[10010];
int n;
void init(){
	int sq = sqrt(n);
	if(sq==0) return;
	for(int i=0;i<n;i++) group[i/sq]+=arr[i]; //대푯값을 구한다.
}
void update(int index,long long val){
    arr[index]=val;
    int sq = sqrt(n);
    if(sq==0) return;
    int groupNum = index / sq; //그룹번호
    int s = groupNum * sq; //그룹의 시작점
    group[groupNum]=0; //group의 합을 다시 계산
    for(int i=s;i<s+sq;i++) group[groupNum]+=arr[i];
}
long long query(int left,int right){
    long long res = 0;
    int sq = sqrt(n);
    if(sq==0){
        for(int i=left;i<=right;i++) res+=arr[i];
        return res;
    }
    while(left<=right && left % sq) res +=arr[left++]; //왼쪽 그룹의 잔여 갯수의 합
    while(left<=right && (right+1) % sq) res +=arr[right--]; //오른쪽 그룹의 잔여 갯수의 합
	//가운데 그룹 갯수의 합을 구하자.
    while(left<=right){
    	res+=group[left/sq];
        left+=sq;
    }
	return res;
}
int main()
{
    //freopen("input.txt","r",stdin);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int m,k;
    long long cmd,a,b;
    cin >> n >> m >> k;
    for(int i=0;i<n;i++) cin >> arr[i];
    init();
    for(int i=1;i<=m+k;i++){
        cin >> cmd >> a >> b;
        if(cmd==1) update(a-1,b);
        else cout << query(a-1,b-1) << "\n";
    }
    return 0;
}

세그먼트 트리보다 시간복잡도는 크지만 세그먼트 트리보다 공간복잡도가 작기 때문에 메모리를 적게 사용해야 할 때 사용할 수 있고 Mo's Algorithm 의 기반이 되는 알고리즘이다.