14. 인덱스 트리(Indexed Tree)

인덱스 트리는 순서를 갖는 정보들이 주었을 때, 구간의 대표값이나 연산 결과를 빠르게 얻을 수 있는 자료구조입니다. 구간의 정보를 빠르게 파악할 수 있는 이유는 정보들을 2진 트리로 구성하여 두 개 노드의 부모노드에 대표값이나 연산결과를 저장했다가 구간이 주어졌을 때 최대한 커버가 가능한 구간 정보부터 압축적으로 정보를 추출하기 때문입니다.

아래와 같이 8개의 정보를 갖고 있는 배열이 주어졌다고 해봅시다. 1 ~ 8자리까지 각 배열의 자리에는 랜덤한 숫자가 주어져 있고 우리는 구간이 주어졌을 때 그 구간의 합이 얼마인지 알고 싶습니다.

1	2	3	4	5	6	7	8
3	2	8	1	2	3	5	6

만일 구간의 합을 구한다고 했을 때 단순하게 계산한다고 하면 매번 그 범위 내에서 for문을 이용하여 합을 구해야할 것이고, 비효율적인 연산을 반복할 것입니다. 우리는 이러한 비효율을 해결하기위해서 인덱스 트리를 사용할 것입니다. 인덱스 트리를 구성하기 위해 두개 노드씩 묶어서 합을 구하고 부모노드에 그 값을 위치시킵니다. 위 배열을 다시 구성해보면 아래와 같습니다.

5 (3 + 2)

9 (8 + 1)

5 (2 + 3)

11 (5 + 6)

3

2

8

1

2

3

5

6

두 노드의 부모노드에는 노드들의 합이 위치합니다 이렇게 반복적으로 부모노드들을 구성해준다고 하면 아래와 같은 형태로 나타나게 될 것입니다.

30

14

16

5

9

5

11

3

2

8

1

2

3

5

6

이제 이렇게 구성된 트리를 하나의 배열로 합쳐보겠습니다. 기존에 주어졌던 배열의 크기의 두 배에 해당하는 배열을 준비하고 루트노드부터 순서대로 배치시킵니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	30	14	16	5	9	5	11	3	2	8	1	2	3	5	6

아직까지는 왜 이런 모양이 되었는지 감이 잘 안올 것입니다. 하지만 잘 생각해보면 노드가 부모노드와 위치적으로 어떻게 연결되어있는지 보일 것입니다. 예를 들어서 기존 배열 기준으로 6 ~ 7구간의 합이 얼마인지 구하고 싶습니다. 원래라면 두 값을 따로 더해주는 연산을 했어야 했지만 이제는 변환된 트리기준 14 / 2 연산을 통해 7이라는 부모노드를 찾아가게 되었을 때 11이라는 합을 갖고 있다는 것을 알 수 있습니다. 1에서 4 구간의 합을 구하는 경우에는 변환된 트리 기준 2의 위치에 그 합인 14가 있다는 것을 알 수 있습니다.

트리를 다시 표현해보자면 전체의 합을 갖고 있는 1번 노드와 절반씩 갖고 있는 2, 3번 노드, 1/4씩 갖고 있는 4 ~ 7번 노드, 그리고 기존 정보를 갖고 있는 8 ~ 15번 노드로 구성되어 있는 것입니다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	30	14	16	5	9	5	11	3	2	8	1	2	3	5	6

색으로 구분하자면 위와 같을 것입니다.

이제 구간이 주어졌을 때 합을 어떻게 구할지 생각해보겠습니다. 구간의 정보를 추출할 때의 특징은 구간으로 주어진 두 숫자가 홀수인지 짝수 인지가 영향을 미친다는 것입니다. 만일 시작하는 위치가 홀수자리였다면 바로 부모값으로 이동하지 못하고 자기 자리는 따로 합에 반영시켜야한다는 특징을 갖고 있습니다. 만일 시작이 짝수번째였고 구간이 끝나는 위치가 시작위치보다 적어도 1보다 큰 수 였다면 바로 자기 부모노드의 합을 가져와도 무관했을 것입니다. 짝수번째 시작이고 구간합에 그 다음번째 자리도 포함되었을 것이기 때문입니다. 가령 기존 배열기준 1 ~ 3 이라면 인덱스 트리기준 8 ~ 10 구간이고 8은 짝수이기 때문에 8, 9 노드의 합인 부모노드 4로 찾아가서 5를 반영해주면 됩니다. 이는 끝나는 위치가 짝수일 때도 동일하게 적용됩니다. 방금 앞에서 말한 케이스에서 10은 끝나는 위치이지만 짝수이기때문에 다음 노드인 11노드의 합이 포함되어있지 않고 부모노드를 구간합에 반영할 수 없습니다. 이 경우에는 당연히 10에 해당하는 수를 따로 더해줘야 할 것입니다. 한마디로 인덱스 트리 기준 시작위치가 홀수라면 그 값을 따로 구간합에 반영해줘야하고 끝나는 위치가 짝수라면 마찬가지로 따로 그 값을 구간합에 반영해줘야 하는 것입니다.

이제 실제 문제를 통해서 구현해보도록 하겠습니다.

2042번: 구간 합 구하기 - Baekjoon Online Judge

https://www.acmicpc.net/problem/2042

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static long[] tree;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine().trim());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        // 2진트리로 표현해야하기 때문에 배열사이즈는 항상 2^n으로 나오게 합니다.
        // 구간합이기 때문에 실제 배열보다 큰 부분은 0으로 채울 경우 계산에 영향을 미치지 않습니다.
        int S = 1;
        while (S < N)
            S <<= 1;
 
        // 사이즈보다 두 배 크게 만들면 기존 배열과 그 부모노드들이 모두 들어갈 수 있는 크기가 됩니다.
        tree = new long[2 * S];
        for (int i = S; i <= S + N - 1; i++)
            tree[i] = Long.parseLong(br.readLine().trim());
        for (int i = S; i <= S + N - 1; i++) {
            int P = i / 2;
            while (P != 0) {
                tree[P] = tree[P] + tree[i];
                P /= 2;
            }
        }
        for (int i = 1; i <= M + K; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if (a == 1) {
                update(S + b - 1, c);
            } else
                System.out.println(sum(S + b - 1, S + c - 1));
        }
    }
 
    private static long sum(int b, int c) {
        long sum = 0l;
        while (b < c) {
            // 시작하는 부분이 홀수인지 판단합니다.
            if ((b & 1) == 1) {
                sum += tree[b];
                b++;
            }
            // 끝나는 부분이 짝수인지 판단합니다.
            if ((c & 1) == 0) {
                sum += tree[c];
                c--;
            }
            b /= 2;
            c /= 2;
        }
        // 밑에서부터 시작과 끝이 올라와서 만나게 된다면 그 구간은 현재 노드가 같은 부모인 것이고,
        // 현재 노드는 하위 모든 노드들의 합을 나타내는 것입니다.
        if (b == c)
            sum += tree[b];
        return sum;
    }
 
    static void update(int idx, long val) {
        long minus = tree[idx];
        int P = idx;
        while (P != 0) {
            tree[P] = tree[P] - minus + val;
            P /= 2;
        }
    }
}