[Algorithm] 세그먼트 트리란?

 

알고리즘

 

 

세그먼트 트리는 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태입니다.

핵심 이론

세그먼트 트리의 종류는 구간 합, 최대, 최소 구하기로 나눌 수 있습니다.

구현 단계에서 구현해야 하는 것은 트리를 초기화하기, 질의 값을 구하기, 데이터 업데이트 하기로 나눌 수 있습니다.

1. 트리 초기화 하기

리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만듭니다.

• $2^k≥N$을 만족하는 k의 최솟값을 구하고 $2^{k+1}$ 크기의 트리 배열을 생성하면 됩니다.
• 또한 리프 노드의 시작 위치를 인덱스로 구해두어야 하는데, 리프 노드의 시작 위치는 $2^k$입니다.

예시

int[] data = {5, 8, 4, 3, 7, 2, 1, 6}

int k = 0;
while (true){
    if(Math.pow(2, k) >= data.length()) break;
    k++;
}

int start_index = (int) Math.pow(2, k);
tree = new long[start_index * 2];

• 여기서 k 값은 3이 되고 따라서 배열의 크기는 16이 됩니다.
• 리프 노드의 시작 위치는 8이 됩니다.

다음으로는 리프 노드들을 채우고 리프 노드의 상위 노드들도 채웁니다.

for(int i = start_index; i < start_index+data.length(); i++){
    tree[i] = data[i - start_index];
}

// 구간합
for(int i = start_index-1; i>0; i--){
    tree[i] = tree[i * 2] + tree[i * 2 +1];
}
// 최대
for(int i = start_index-1; i>0; i--){
    tree[i] = Math.max(tree[i * 2], tree[i * 2 +1]);
}
// 최소
for(int i = start_index-1; i>0; i--){
    tree[i] = Math.min(tree[i * 2], tree[i * 2 +1]);
}

• 구간 합 : 자식 노드들을 더한 값이 자신의 값이 됩니다.
• 최대 : 자식 노드들 중 더 큰 값이 자신의 값이 됩니다.
• 최소 : 자식 노드들 중 더 작은 값이 자신의 값이 됩니다.

2. 질의값 구하기

질의 인덱스를 세그먼트 트리 인덱스로 변경

• 보통 질의 인덱스는 리프 노드들의 원래 인덱스를 말하는 경우가 많습니다.
• 이 경우 세그먼트 트리 인덱스로 변경해주어야 합니다.

세그먼트 트리 index = 질의 index + $2^k-1$

질의값 구하기 (구간)

1. start_index % 2 == 1 일때 해당 노드를 선택합니다.
2. end_index % 2 == 0 일때 해당 노드를 선택합니다.
3. start_index = ( start_index+1) / 2 로 갱신합니다.
4. end_index = (end_index - 1) / 2 로 갱신합니다.
5. start_index ≤ end_index가 될때까지 반복합니다.

질의 결과 도출

• 구간 합 : 위의 1, 2에서 선택된 노드들을 모두 더합니다.
• 최댓값 구하기 : 위의 1, 2에서 선택된 노드들 중 가장 큰 값을 선택합니다.
• 최솟값 구하기 : 위의 1, 2에서 선택된 노드들 중 가장 작은 값을 선택합니다.

// 구간 합
static long rageSum(int start_index, int end_index){
        long sum = 0;

        while (start_index <= end_index){
            if(start_index % 2 == 1) sum += tree[start_index];
            if(end_index % 2 == 0) sum += tree[end_index];

            start_index = (start_index+1) /2;
            end_index = (end_index -1)/2;

        }
        return sum;
    }

3. 데이터 업데이트 하기

• 구간 합 : 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경합니다.
• 최댓값 구하기 : 변경 데이터와 같은 부모를 가지는 노드와 비교하여 더 큰 값으로 부모 노드를 업데이트 합니다.
• 최솟값 구하기 : 변경 데이터와 같은 부모를 가지는 노드와 비교하여 더 작은 값으로 부모 노드를 업데이트 합니다.

// 구간 합 예시
static void changeNumber(int index, long value){
    long diff = value - tree[index];

    while (index > 0){
        tree[index] += diff;
        index /= 2;
    }
}