자료구조) 세그먼트 트리, segment tree

당신이 만약 백준 플래티넘 티어에 도전하는 모험가라면 부스터 한개는 남겨놓았길 바란다.

 

세그먼트 트리

최소 골드 2부터 시작하는 쉽지 않은 알고리즘임에도 불구, 트리를 초기화 및 업데이트하고 누적합만 구하는 accumulator가 된다면, 골1 수문장은 쉽게 돌파할 수 있을 것이기 때문이죠.

---

세그먼트 트리는 데이터 배열에서 특정 범위에 대한 쿼리를 효율적으로 수행하는 균형 잡힌 이진트리 형태의 자료구조로

• 트리의 리프 노드는 전체 배열의 단일 요소를 표현하며,
• 트리 내부의 각 노드는 요소의 범위를 나타냅니다.

 트리의 각 내부 노드는 상위 노드가 표현하는 범위의 왼쪽과 오른쪽을 절반씩 나타내는 두 개의 하위 노드를 가지며, 상대적으로 적은 수의 노드로 어레이의 전체 범위를 나타낼 수 있으며 범위 값의 수정과 검색에 있어 O(logN)의 연산이 필요합니다.

 여기서 상대적으로 적은 노드라는 표현은 테이블 구조에 대한 상대성을 의미하며, 실제로 변경이 없고 메모리가 여유 있는 경우 N^2 크기의 테이블을 통해 O(1)의 시간 복잡도로 특정 범위의 검색이 가능합니다.

 

 세그먼트 트리는 위와 같은 특정 케이스를 제외한 보다 범용적인 상황에서 특정 범위 내의 최소/최댓값, 누적 합, 누적 곱을 구하고 수정하는 쿼리를 통해 배열에 대한 다양한 작업을 수행할 수 있습니다.

 

N 개의 자료를 전처리해 세그먼트 트리의 구조로 만들기 위해서는 깊이를 log2(N)로 가지는 이진 트리가 필요하기 때문에 2 ^ ceil( log2(N) ) + 1개의 크기를 가지며, 배열의 크기 * 4를 했을 때 항상 해당 식보다 크거나 같은 값이 나오기 때문에 메모리를 타이트하게 가져가지 않는다면 저렇게 여유를 주어도 됩니당. (4개일 땐 8, 5개일 땐 16개의 배열 개수 필요)

 

이제 세그먼트 트리의 라이프 사이클을 보면 처음 트리를 초기화하는 과정과 트리가 도중에 업데이트되는 과정, 트리를 이용해 특정 구간의 값을 구하는 과정으로 크게 세 부분으로 구분됩니다.

 

---

초기화

재귀적으로 초기화가 진행된다.

1번 노드가 루트 노드가 되며, 모든 노드는 상위 노드의 범위의 절반을 표현. 즉 리프 노드들은 각자의 독립적인 값을 가지며, 루트 노드는 항상 전체 범위를 대표하는 값을 가진다.

 

int array[n];
int segtree[1 << (int)ceil(log2(n) + 1)];

void init(int node, int rangeS, int rangeE) {
	if (rangeS == rangeE) {	//	서브트리를 가지지 않는 리프노드는 독립적인 값을 가짐
    	segtree[node] = array[rangeS];
        return ;
    }
    int middle = rangeS + (rangeS + rangeE) / 2;
    
    init(node * 2, rangeS, middle);
    init(node * 2 + 1, middle + 1, rangeE);
    segtree[node] = 대충 comp(segtree[node * 2], segtree[node * 2 + 1]);
}

현재의 범위를 두 개의 범위로 분해한 후 하위 서브 트리들의 초기화가 완료되면 이를 통해 자기 자신의 대푯값을 설정함

---

업데이트

범위를 절반씩 나누어가며 현재 범위에 수정하려는 인덱스가 포함되지 않는다면 연산 종료.

해당 요소를 나타내는 리프 노드에 도착했다면 해당 값을 수정 후, 호출된 함수들을 탈출하며 업데이트된 값으로 다시 연산함

int child_update(int child_1, int child_2) {
	//	return max(TREE[child_1], TREE[child_2]);
    //	return min(TREE[child_1], TREE[child_2]);
    //	return sum(TREE[child_1], TREE[child_2]);
    //	etc ..
}

void update(int node, int rangeS, int rangeE, int idx, int afterValue) {
	if (rangeS > idx || idx > rangeE) return ;	//	찾으려는 값이 범위 내에 없으면 종료
    /**
     *	시작과 끝이 같은 상황, 찾으려는 인덱스의 값을 나타내는 리프노드에 도착했다면
     *	리프 노드의 값을 수정하고 재귀 호출 탈출
     */
    if (rangeS == rangeE) {
    	TREE[node] = afterValue;
        return ;
    }
    int child_1 = node * 2, child_2 = node * 2 + 1;	//	자식 노드
    int mid = rangeS + (rangeE - rangeS) / 2;
    update(child_1, rangeS, mid, idx, afterValue);
    update(child_2, mid + 1, rangeE, idx, afterValue);
    //	범위 값의 변경이 일어났으니 상위 노드 수정
    TREE[node] = child_update(child_1, child_2);
}

diff 값을 받아 호출 전 노드의 범위에 선반영 하는 등 다양한 바리에이션이 존재함

---

구간 값 인출

각 호출은 찾으려는 시작 범위(from) - 끝 범위(to)와 현재 노드가 나타내는 범위 rangeS - rangeE에 따라 다음과 같은 케이스가 생김

1. 찾으려는 범위가 현재 노드의 범위 내에 전부 포함되는 경우
2. 찾으려는 범위가 현재 범위와 조금도 겹치지 않는 경우
3. 찾으려는 범위가 현재 노드 범위에 시작 또는 끝부분이 걸치는 경우

 

const int DEFAULT_VALUE = 0;

int child_compute(int child_1, int child_2) {
	//	return max(TREE[child_1], TREE[child_2]);
    //	return min(TREE[child_1], TREE[child_2]);
    //	return sum(TREE[child_1], TREE[child_2]);
    //	etc ..
}

int search(int node, int rangeS, int rangeE, int from, int to){
    if (to < rangeS || rangeE < from) return DEFAULT_VALUE;	//	#CASE 2
    if (rangeS <= from && to <= rangeE) return TREE[node];	//	#CASE 1
    
    //	#CASE 3
    int child_1 = node * 2, child_2 = node * 2 + 1;
    int mid = rangeS + (rangeE - rangeS) / 2;
    return child_compute(	//	하위 두개의 노드를 검색해서 나온 값으로 반환 값 계산
    	search(child_1, rangeS, mid, from, to),
        search(child_2, mid + 1, rangeE, from, to)
    );
}

1번에서는 찾으려는 범위 내에 해당 범위가 모두 들어있으므로 곧바로 값을 반환

2번에서는 찾으려는 범위와 전혀 상관없는 범위이므로 곧바로 불필요한 연산 종료

3번 같은 경우에는 불필요하게 겹쳐있는 값을 반으로 쪼개 절반은 CASE1, 나머지 절반은 CASE2이 될 때까지 동일 연산을 반복해 필요한 범위의 값만 뽑아냄