[자료구조] 세그먼트 트리 (Segment Tree)

  목  차

• 세그먼트 트리 개념
• 세그먼트 트리를 하며 배운 것들
• 세그먼트 트리 코드

 

 

---

 

  세그먼트 트리 개념

 

세그먼트 트리는 구간 쿼리와 업데이트를 최적으로 수행할 수 있는 유연한 자료구조이다. 주로 구간 합, 또는 구간 내 최솟값이나 최댓값을 찾는 문제에 사용된다.

 

 

  기본 구조

 

트리 구조: 세그먼트 트리는 이진 트리 구조이며, 각 노드는 배열의 특정 구간(Segment)을 대표한다.

리프 노드: 트리 구조에서 자식 노드가 없는 노드를 말한다. 즉 트리 가장 아래에 위치한 노드들을 말한다.

내부 노드: 자식 노드들의 값을 합치거나 비교하여 해당 구간의 값을 저장한 노드들을 말한다.

 

 

  작동 원리

 

트리 초기화: 주어진 배열로 완전 이진 트리를 만든다. O(N)

SUM함수: 구간합을 구하는 함수 O(log N)

UPDATE함수: 특정 요소가 업데이트 될 때, 해당 요소를 시작으로 트리를 업데이트한다. O(log N)

 

 

---

 

  세그먼트 트리를 하며 배운 것들

 

JavaScript 기준으로 작성하였습니다.

 

 

  Number와 BigInt

 

Number 타입은 -2^53 부터 2^53 사이의 정수값을 정확히 표현할 수 있다.

 

BigInt 타입은 그 이상의 숫자도 정확히 표현할 수 있다. 다만 소수점 아래의 숫자는 표현할 수 없다.

그리고 BigInt는 숫자 뒤에 n을 붙여서 표현할 수 있다.

 

 

백준 알고리즘에서 문제번호 2042인 세그먼트 트리 문제에서는 답이 -2^63~(2^63)-1 사이라고 알려준다. 이는 Number 타입으로는 표현할 수 없으므로 BigInt를 사용해야 한다는 의미이다.

 

그리고 Number 타입과 BigInt 타입의 숫자는 서로 연산할 수 없다.

 

알고는 있었지만 이번에 뼈저리게 느끼면서 뇌리에 박히게 되었다.

 

 

  시프트 연산

 

<<= 부호로 비트를 한 칸 옮겨서 숫자를 2배씩 증가시킨다.

 

완전 이진트리를 만들기 위해서 방법을 찾아보다 시프트 연산에 대해서 알게 되었다. 

아래는 N이 20일 때 N 보다 크지만, 가장 작은 2의 제곱수를 찾는 코드이다.

 

const N = 20;
let pow = 1;
while(pow <= N){
	pow <<= 1;
}

 

 

시프트 연산 없이 수학적으로도 가능한데 초보자인 나는 처음 보고 이게 뭔 코드지 했지만, 이해하고 나서는 아래 코드가 더 쉬웠다. 하지만 시프트 연산이 더욱 간결하고 가독성도 좋다고 생각한다.

 

 

아래는 수학적으로 해결한 케이스이다.

 

const N = 20;
const pow = 2 ** Math.ceil(Math.log2(N));

 

 

먼저 Math.ceil()은 인자로 들어온 값을 올림 하는 함수이다. 예를 들면, 4.2가 들어온다면 5를 반환한다.

다음으로 Math.log2() 함수는 인자의 로그값을 반환하는 함수이다.

 

 

 

---

 

  세그먼트 트리 코드

 

 

initTree 메서드:

재귀 함수보다는 for문으로 간단하게 구현했다. 아직은 재귀보다는 반복문이 편하기 때문이다.

 

sum 메서드:

구해야 하는 값의 구간이 왼쪽 혹은 오른쪽 구간에 포함되지 않으면 그냥 바로 0을 반환한다.

 

그리고 sum 메서드에 재귀 부분에서 Math.min과 Math.max 함수가 사용되었는데, 그 이유는 그냥 half를 사용하면 구할 값의 구간이 커지거나 작아지기 때문이다. (이 함수들은 입력된 인자들 중에서 가장 작은 혹은 가장 큰 인자를 반환한다.)

 

추가로 최적화 하는 부분인데, 재귀 부분에서 left <= half 혹은 right > half 조건문을 추가하는 것으로 최적화를 할 수 있다.

 

update 메서드:

이 메서드는 다소 간단하다. 리프 노드로 부터 시작되어서 전체적인 트리를 업데이트한다.

 

 

개인적인 주요 포인트는 4가지 라고 생각한다.

1. 자바스크립트에서는 BigInt를, C++의 경우에는 long long을 사용한다.
2. SUM: Math.min과 Math.max를 적절히 사용하여 범위가 커지는 것을 방지한다.
3. 완전 이진 트리를 잘 구현한다.
4. console.log()를 했을 때 숫자 뒤에 n이 붙지만 그대로 제출한다면 자동으로 n을 없애주니 문자열로 변환하고 n을 없앤 후 다시 BigInt로 변환하는 뻘짓은 하지말자..

 

 

class SegementTree {
	
	constructor(arr, N, start = 1, end = N){
		this.arr = arr;
		this.width = 2 ** Math.ceil(Math.log2(N))
		this.N = N;
		this.tree = new BigInt64Array(2 * this.width).fill(0n);
		this.start = start;
		this.end = end;
	}

	// 트리 초기화 메서드
	initTree(node = 1, start = this.start, end = this.end){
    for(let i = 0; i < N; i++){	
			this.tree[this.width + i] = this.arr[i + 1];
		};

		for(let i = this.width - 1; i > 0; i--){
			this.tree[i] = this.tree[i * 2] + this.tree[i * 2 + 1]
		};
	}

	// node: 루트노드, start: 현재 노드의 역할 시작 값, end: 현재 노드의 역할 끝 값, left: 구할 값 구간, right: 구할 값 구간
	sum(node, start, end, left, right){
		
		if(start == left && end == right) {
			return this.tree[node]
		} else if(left > right){
			return 0n
		}

		const half = Math.floor((start + end) / 2)
		
		let node_left = node * 2;
		let node_right = node * 2 + 1;
	
		const left_sum = 
        	left <= half ? 
       	 	this.sum(node_left, start, half, left, Math.min(right, half)) 
        	: 0n;

		const right_sum = 
        	right > half ? 
        	this.sum(node_right, half+1, end, Math.max(left, half+1), right) 
        	: 0n;
		

		return left_sum + right_sum
	}
	

// index 초기값: b, value: c
	update(index, value){
	    let node = this.width + index - 1
		let diff = value - this.tree[node];


        let parent = node
        while(parent > 0){
            
            this.tree[parent] += diff
            parent = Math.floor(parent / 2);
            
        }
	}

	
}