Query 정리

목차

구간 질의

정적배열인경우

누적합

• prefix sum array

위의 누적합 배열을 사용할때, $[a,b]$에 속하는 원소들의 합을 $\text{sum}(a,b)$이라고 한다면

위치 k의 원소는 $\text{sum}(0,k)$이 되는데, 이떄 이 값들을 모두 미리 구해논다면 전처리를 $O(N)$에 수행할 수 있고, 질의에는 $O(1)$만 걸리게 된다.

Mo’s Algorithm

Mo’s Algorithm 을 이용하면 정적배열에서 Query를 정렬시켜 $O(Q+T(N) N \sqrt N)$ 안에 풀수 있게 해준다.

정적 배열이 아닌경우

원소갱신 업데이트가 있는 경우 이 작업을 수행하는데 로그 시간이 걸리는 자료구조를 사용한다.

Fenwick Tree

펜윅 트리를 구성할 때에는 1-based array를 사용한다. 또한 사용할 배열의 크기는 단순히 기존 배열의 크기와 동일하다.

$p(k)$는 k 의 약수중 $2^i$에 해당하는 수들에서 가장 큰 수로 정의한다면, 해당 자료구조에 저장할 수는 다음과 같다.

위 수식을 풀어서 설명하면 배열 위치 $k$에 저장되는 값은 원래 배열에 대해 위치 $k$에서 끝나면서 그 길이가 $p(k)$인 구간의 합을 의미한다.

이 $p(k)$는 $k$를 binary로 나타내었을때, $k$의 비트 1 중에서 최하위 비트 한개만 남기는 것과 같은 의미이다.

그 값이 바로 $\text{tree}[k]$에서 저장될 누적합의 길이와 같다.

그리고 이는 $k \& -k$ 로 나타낼 수 있다.

const int SZ = 101010;
int tree[SZ];

int sum(int k){
	int s= 0;
	while(k>=1){
		s += tree[k];
		k -= k& -k;
	}
	return s;
}

void add(int k, int x){
	while(k <= SZ){
		tree[k] += x;
		k+= k& -k;
	}
}

다음처럼 Fenwick tree를 구현할 수 있다.

segment tree(구간트리)

세그먼트트리 또한 로그시간을 사용하는 트리를 이용한 자료구조이다. 누적합을 사용하는 펜윅 트리와는 다르게, 구간합을 제외한 range minimum , range maximum 등 다양한 질의를 수행할 수 있는 것이 장점이다.

세그먼트 트리의 구현은 이곳에서 참조하면 된다.

Sqrt Decomposition

Sqrt Dcomposition은 Segment tree 보다 성능은 좋지 못하지만 , Mo’s algorithm을 수행 할 때 필요한 알고리즘이다.

전처리에는 $O(\sqrt(N))$, 질의에는 $O(\sqrt(N))$ 이 걸린다.

ll arr[SZ], bucket[bSZ];
int p, n , m ,k;

void build(){
	p = sqrt(n);
	for(int i = 1; i<=n;i++){
		bucket[i/p] += arr[i];
	}
}

void update(int idx, ll k){
	arr[idx] = k;
	int bid = idx/p;
	bucket[bid] = 0;
	for(int i = bid * p; i<bid * p+p ;i++) bucket[bid] += arr[i];
}

ll query(int l, int r){
	ll ret = 0;

	while(l%p != 0 && l <= r) ret += arr[l++];
	while((r+1)%p != 0 && l <= r) ret += arr[r--];
	while(l <= r){
		ret += bucket[l/p];
		l += p;
	}
	return ret;
}