Segment Tree

 

 

 

 

Segment Tree

세그먼트 트리

 

구간 별 정보를 저장하는 트리 구조로

업데이트가 빈번히 일어나거나 구간이 주어지는 쿼리문을 해결하기 좋다.

가장 유명한 예시로 구간 합이나 구간 내 최대/최솟값을 찾는 문제가 있다.

쿼리에 따라 정보를 저장하면 된다.

 

 

---

 

 

배열의 원소는 트리 상 리프(leaf)에 존재하며,

Root를 기준으로 왼쪽과 오른쪽에 동일(하거나 한 개 차이)한 개수의 리프 정보에 대해 저장한다.

N=8처럼 N=$2^n$꼴이라면 모든 노드에 대해 정확히 절반의 리프 정보를 왼쪽/오른쪽 자식 노드에 저장해 포화이진트리를 만들 수 있다. N=6, 7인 경우 아래와 같이 트리를 만든다.

 

아래 특징을 기억하면 된다.

• $n$번 노드의 왼쪽 자식 노드는 $2n$번, 오른쪽 자식 노드는 $2n+1$번이다.
• $n$번 노드가 $m$개의 리프를 다루면
  왼쪽 자식 노드는 $\left \lceil \frac{m}{2} \right \rceil$개, 오른쪽 자식노드는 $\left \lfloor \frac{m}{2} \right \rfloor$개 리프를 다룬다.

 

---

 

example. 수열과 쿼리 16

원소의 개수가 N개인 수열 A에 대하여 아래 두 쿼리를 수행하도록 세그먼트 트리를 만들자.

• Ai(1 ≤ i ≤ N)를 v로 바꾼다.
• Ai부터 Aj까지(1 ≤ i ≤ j ≤ N) 수열의 원소 중 최솟값의 인덱스를 구한다.

 

 

 

Tree Build

int Build(int n, int s, int e) {
	if (s == e) return T[n] = s;
	
	int m = (s + e) >> 1;
	int L = Build(n << 1, s, m);
	int R = Build((n << 1) + 1, m + 1, e);
	T[n] = (A[L] <= A[R]) ? L : R;

	return T[n];
}

 

 

Query1 (Update)

void Update(int n, int s, int e, int idx) {
	if (s != e) {
		n <<= 1;
	
		int m = (s + e) >> 1;
		if (idx <= m) Update(n, s, m, idx);
		else Update(n + 1, m + 1, e, idx);
		
		T[n >> 1] = (A[T[n]] <= A[T[n + 1]]) ? T[n] : T[n + 1];
	}
}

* 당연히 n을 두 배 해주고 나눠주고 하는 건 편한대로 하면 된다

 

 

Query2

int Query(int n, int s, int e, int i, int j) {
	if (s == i && e == j) return T[n];

	n <<= 1;
	int m = (s + e) >> 1;
	if (j <= m) return Query(n, s, m, i, j);
	else if (i > m) return Query(n + 1, m + 1, e, i, j);
	else {
		int L = Query(n, s, m, i, m);
		int R = Query(n + 1, m + 1, e, m + 1, j);
		return ((A[L] <= A[R]) ? L : R);
	}
}

 

 

 

각 함수는 쿼리에 맞게 구현하면 된다.

수열과 쿼리 시리즈를 풀면 될 듯.

아직 나도 많이 안 풀어봤는데, 기본적인 세그먼트트리 구현을 연습하기도 좋고 관련한 다른 알고리즘을 공부하기도 좋다.

 

---

 

사실 이 방식은 최근에 공부한 거고, 그전엔 세그트리를 포화이진트리로 구현했다.

포화이진트리로 구현하면 빌드나 업데이트에서 bottom-up으로 해결하기는 쉽지만

모든 리프가 같은 깊이 상에 존재하기 때문에 시간이 약간 더 오래걸린다.

그리고 2의 n제곱 계산이 너무 헷갈리고 코드 가독성도 안 좋아서,,, 다른 방법을 다시 익혔다.

 

 

 

포화이진트리로 구현하면 트리 빌드는 편했다.

재귀로 구할 필요도 없고, 단순하게 생각하기는 굉장히 편했다.

가령 빌드는 아래처럼 구현함. 쿼리함수는 위와 비슷하게 구현하면 된다.

int TWO = 1;
while (N > TWO) TWO <<= 1;

int idx = TWO;
while (idx) {
	for (int i = idx; i < (idx << 1); i += 2) {
		T[i >> 1] = (T[i] + T[i + 1]);
	}
	idx >>= 1;
}

 

 

그치만 이 방식은 뭔가 필요없는 연산이 많아지는 느낌

가령 수열의 원소 개수가 $2^n+1$개라면 포화 이진트리의 성능은 최악이다.

$2^{n+1}$개의 리프 노드 중 버리는 노드가 절반($2^n-1$)이다.

N=5이면 불필요한 리프 노드가 3개지만 N=65면 63개나 된다.

구현도 그렇고 이런 면에서도 위의 방법이 더 편한 듯!