Sqrt Decomposition

Introduction

Sqrt Decomposition이란 구간을 $\sqrt{n}$개의 bucket으로 나눠 쿼리를 $O(\sqrt{n})$ 만에 처리하는 테크닉이다.

물론 세그먼트 트리를 이용하면 $O(\log{n}) $만에 구간 쿼리를 계산할 수 있지만, Sqrt Decomposition 은 Mo's Algorithm에 기반이 된다고 하니 배워보자.

 

코드

아래의 코드는 이 문제를 기준으로 작성되었다.

#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

const int MAX = 1000000001, MIN = 0;

struct Ele {
	int min, max;
};

int n, m, sqr;
Ele arr[100001], bucket[400];

inline Ele Calculate(Ele e1, Ele e2) {
	return { min(e1.min, e2.min), max(e1.max, e2.max) };
}

void Init(void) {
	
	sqr = ceil(sqrt(n));

	for (int i = 0; i < sqr; i++)
		bucket[i] = { MAX, MIN };

	for (int i = 0; i < n; i++)
		bucket[i / sqr] = Calculate(bucket[i / sqr], arr[i]);

	return;
}
void Update(int idx, int val) {

	arr[idx] = { val, val };

	bucket[idx / sqr] = { MAX, MIN };

	for (int i = 0; i < sqr; i++)
		bucket[idx / sqr] = Calculate(bucket[idx / sqr], arr[(idx / sqr) * sqr + i]);

	return;
}
Ele Query(int ts, int te) {

	Ele ans = { MAX, MIN };
	
	for (int i = 0; i < sqr; i++) {
		int s = i * sqr, e = i * sqr + sqr - 1;
		
		if (e < ts || te < s)
			continue;
		
		else if (ts <= s && e <= te)
			ans = Calculate(ans, bucket[i]);

		else {
			for (int j = max(s, ts); j <= min(e, te); j++)
				ans = Calculate(ans, arr[j]);
		}
	}

	return ans;
}

int main(void) {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		arr[i] = { x, x };
	}

	Init();

	for (int i = 0; i < m; i++) {
		int s, e;
		scanf("%d %d", &s, &e);

		Ele a = Query(s - 1, e - 1);

		printf("%d %d\n", a.min, a.max);
	}

	return 0;
}

 

함수 설명

 

Calculate : 요소에 대한 연산으로 이 함수를 수정함으로써 구간 합을 처리하는등 으로 바꿀 수 있다.

 

Init : 모든 bucket을 $O(n)$ 만에 초기화 한다.

 

Update : 한 요소의 값을 업데이트 하는 함수로, $O(\sqrt{n})$ 만큼 걸린다.

 

Query : 하나의 쿼리를 처리하는 함수로, $O(\sqrt{n})$ 만큼 걸린다.