[Algorithm] 인덱스 트리(Indexed Tree)

 구간 합을 구하는 트리의 종류로 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있다. 세그먼트 트리는 인덱스 트리가 포함하고 있는 한 종류이다.

 

 

세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있다.

 

 

 

 

인덱스 트리란 ?

 

 

 

 이진 트리의 한 종류로서 구간 합을 구하는데 쓰이는 자료구조.

 

예를 들어, 배열 A에 수열이 들어있고 구간 S-E 가 주어졌을때 

 

① A[S] - A[E] 의 구간합을 구하고

② 구한 뒤 특정 A[i]번째 원소가 다른 숫자로 바뀐다. 

 

①② 번 작업을 반복하는 일이 있을 때 인덱스 트리를 쓰게 된다.

 

 

 

만약 1,2,3,4 라는 수열이 배열에 들어있다고 하면 수의 갯수를 모두 리프노드에 넣을 수 있을만큼의 배열을 잡아야한다.

 

아래 그림에서 4,5,6,7 번에 1,2,3,4 가 들어가면 리프노드에 모든 숫자를 넣을 수 있는 트리구조를 만들 수 있다.

 

 

 

 

 

즉 1,2,3,4 -> 4개의 수를 모두 리프 노드에 넣을 수 있는 트리를 연속 구조 방식(배열) 으로 표현한다.

 

0번째 배열 위치는 사용하지 않는다.

 

만약 숫자가 9개라면 리프 노드의 개수는 트리의 높이를 h라 했을때 2^h 이므로 9 <= 2^h 인 h 값은 4이다.

 

따라서, 크기가 16개인 배열을 선언하고 배열 인덱스 8번부터 9개의 숫자를 채우고 빈 공간은 0으로 채운다.

 

 

 

 

 

위의 사진은 1,2,3,4 를 리프 노드에 모두 넣을 수 있는 트리의 연속 구조이다.

 

이와같이 구조를 세운다음 자식노드들의 합을 부모 노드에 저장한다.

 

부모가 i 번째이면 왼쪽 자식은 i*2이고 오른쪽 자식은 i*2+1 이다. 이점을 이용하여 모든 자식 노드의 합을 부모 노드에 기록한다.

 

배열의 3번째 위치에는 6번째 + 7번째

배열의 2번째 위치에는 4번째 + 5번째

배열의 1번째 위치에는 2번째 + 3번째

 

이러한 방식으로 모두 채우고 나면

 

 

 

이러한 형태의 트리가 만들어 진다. 각 노드에 있는 값들은 자식 노드 value 값들의 합이다.

 

 

 

 

 

● 구간 합 구하기

 

 

여기서 우리는 구간합을 구할 수 있는데, 아래 그림을 참고하자.

 

 

 

네모칸은 배열에 value가 저장되어 있는 index이고 노드의 번호들은 value 값을 나타낸다.

 

여기서 2~4까지의 구간합은 얼마일까??

 

숫자가 너무 작고 범위도 작아 한눈에 구할 수 있지만 인덱스 트리로 구하여 보자.

 

 

구간의 왼쪽 끝을 L 오른쪽 끝을 R 이라고 했을 때,

 

L과 R이 왼쪽 자식인경우와 오른쪽 자식인 경우로 나눌 수 있다. 위 그림에서 L 은 2번째 노드의 오른쪽 자식이고 R은 3번째 노드의 오른쪽 자식이다.

 

무슨 말을 하려는 거지??? 라고 생각 할 수 있다.

 

1) L 의 경우

 

현재 2가 저장된 5번째 노드를 보자. 5번째 노드의 부모인 2번째 노드에는 4번째 노드와 5번째 노드의 합인 3이 저장되어 있다.

 

즉, 우리는 3번째 노드에서 4번째 노드의 값을 뺀 2라는 값만 필요하다. 왜냐면 2~4까지의 구간합을 구하는거니까 4번째 노드에 저장되어 있는 1은 필요없다. 즉, L 오른쪽 구간에 대해서 값을 더해나가는게 목적이지 L 의 왼쪽 구간에 대해서는 값을 계산할 필요가 없다.

 

 만약 1~4까지를 구하는 것이었다면 5/2 = 2 (연속 구조 안에서 부모 노드로 가는 방법) 를 해서 부모노드로 올라가 값을 구하면 되지만 1은 필요 없기 때문에 2라는 값만 구간 합을 계산하는 변수에 저장하고 배열 인덱스를 +1 시켜준다. 즉 6번째 노드를 가리키게 된다.

 

만약 L+1 을 했을 때 그값이 R 과 같다면 그 값을 합 계산 변수에 더해주고 루프를 마무리한다.

 

반면 L 이 왼쪽 노드라면 4/2 =2  2번 노드로 가게된다.

 

 

 

 

2) R 의 경우

 

현재 R은 오른쪽 자식 노드이기 부모 노드로 가면 된다. 즉 R 의 오른쪽 값을 볼 필요가 없다. 따라서 7/2 =3  3번 노드로 가게된다.

 

R 이 왼쪽 노드라면 L 이 했던 경우처럼 구간 합을 계산하는 변수에 현재 값을 더하고 -1을 한다.

 

 

 

 

 

이러한 방식으로 구간합을 계산할 수 있다.

 

수행시간 lg N

 

 

 

● 값 업데이트 시키기

 

 

특정 원소 A[i] 가 바뀌었다면 현재 값과 새로운 값의 차이만큼 루트노드로 올라가면서 값을 갱신 시켜주면 된다.

 

수행시간 : lg N

 

 

 

 

https://www.acmicpc.net/problem/2042 (구간 합 구하기)

 

인덱스 트리를 활용할 수 있는 기본 문제이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
 
 
long long getindex(int N) {
    int temp = 1;
    while (temp < N) {
        temp = temp << 1;
    }
 
    return temp * 2;
}
 
int main() {
 
    vector <long long> v(8194304 + 1, 0);
 
    int N, M, K; //수의개수, 변경 일어나는 횟수, 구간의 합을 구하는 횟수
 
    cin >> N >> M >> K;
 
    long long index = getindex(N);
    long long p = index / 2;
    //cout << index << '\n';
    for (int i = 0; i < N; i++) {
        cin >> v[p];
        p++;
    }
    for (int i = (index / 2) - 1; i > 0; i--) {
        v[i] = v[i * 2] + v[i * 2 + 1];
    }
    //합구함.
 
    
    for (int i = 0; i < M + K; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
 
        if (a == 1) {//b 번째 수를 c 로 바꾼다.
            long long idx = (index / 2) + (b - 1);
 
            long long pp = idx;
            if (v[idx] < c) {
                long long gap = c - v[idx];
                v[idx] += gap;
                pp >>= 1;
                while (pp > 0) {
 
                    v[pp] += gap;
                    pp >>= 1;
                }
            }
            else {
                long long gap = v[idx] - c;
                v[idx] -= gap;
                pp >>= 1;
                while (pp > 0) {
                    v[pp] -= gap;
                    pp >>= 1;
                }
            }
        }
 
        if (a == 2) { // b 번째 수부터 c번째 수까지의 합
            long long L = (index / 2) + (b - 1);
            long long R = (index / 2) + (c - 1);
 
            long long S = 0;
 
            while (L <= R) {
 
 
                if (L % 2 == 0) {
                    L /= 2;
                }
                else {
                    S += v[L];
                    L++;
                    if (L == R) {
                        S += v[L];
                        break;
                    }
                    else {
                        L /= 2;
                    }
                }
 
                if (R % 2 == 0) {
                    S += v[R];
                    R--;
                    R /= 2;
                }
                else {
                    R /= 2;
                }
 
            }
 
            cout << S << '\n';
        }
    }
 
 
 
    return 0;
 
 
 
}