구간 트리(세그먼트 트리)

세그먼트 트리

 

저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 답할 수 있도록 하는 방법이다.

구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것이다.

구간 트리의 루트는 항상 배열의 [0,n-1]을 표현한다.

구간 트리

구간 트리에서 질의에 응답하는 시간복잡도는 O(logn)이다.

 

구간 트리에서 구간을 모두 저장하기 위한 배열의 길이는 n이 2의 거듭제곱이라면 2n이면 된다. 그렇지 않다면 가장 가까운 2의 거듭제곱으로 n을 올림한 뒤 2를 곱해야 한다. 

하지만 간단한 방법으로 4n으로 배열의 길이를 잡으면 된다. 메모리가 낭비된다는 단점이 있지만 편리하게 쓸 수 있다.

 

 

 

구간 트리 초기화

 

static long init(int node, int s, int e) {
	if(s==e)
		return tree[node]=arr[s];
	int mid = (s+e)/2;
	return tree[node]=init(node*2,s,mid)+init(node*2+1,mid+1,e);
}

 

예시로 구간 합을 위해 구간 트리를 초기화 하는 것을 보여준다.

구간 트리의 배열의 시작을 1부터 하여 왼쪽 자식의 인덱스가 node*2, 오른쪽 자식의 인덱스가 node*2+1이 될 수 있도록 한다.

s==e 지점은 트리의 리프 노드에 해당한다.

그 이외의 지점에는 왼쪽 자식과 오른쪽 자식의 합을 저장한다.

 

 

구간 트리 질의 응답

 

static long sum(int L, long R, int node, int nodeL, int nodeR) {
	if(nodeL > R || nodeR < L) return 0;
	if(L <= nodeL && nodeR <= R) return tree[node];
	int mid = (nodeL+nodeR)/2;
	return sum(L,R,node*2,nodeL,mid)+sum(L,R,node*2+1,mid+1,nodeR);
}

 

L부터 R까지의 범위 의 합을 구하는 함수이다.

만약 탐색하는 구간이 구하고자 하는 범위와 상관이 없으면 0을 리턴한다.

탐색하는 구간이 원하는 구간이라면 구간 트리에 저장되어 있는 값을 리턴한다.

그 외의 범위는 왼쪽 자식, 오른쪽 자식에서 찾은 값을 더해서 리턴한다.

 

 

구간 트리 갱신

 

static long update(int i, long val, int node, int s, int e) {
	if(i < s || e < i) return tree[node];
	if(s == e) {
		return tree[node] = val;
	}
	int mid = (s+e)/2;
	return tree[node] = update(node*2,i,val,s,mid)+update(node*2+1,i,val,mid+1,e);
}

 

i번째 값을 val로 바꾸는 작업을 하는 함수이다.

s==e가 되는 지점은 리프 노드에 해당하므로 값을 val값을 현재 노드에 넣어준다.

그 외의 지점은 왼쪽 자식과 오른쪽 자식의 합으로 갱신해준다.

 

참고 문제

http://boj.kr/2042

2042번: 구간 합 구하기

http://boj.kr/11505

11505번: 구간 곱 구하기