15. 인덱스 트리

트리 구조로 구간 합 구하기

• 세그먼트 트리는 구현 과정이 복잡하고 어려워 더 쉽게 구할 방법이 필요
• 인덱스 트리는 간단하며 O(log N)의 시간복잡도 가짐
• 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성도 높음

인덱스 트리의 원리

특정한 숫자의 마지막 비트 구하기

마지막 비트를 이용해 트리 구조 만들기

인덱스 트리 1부터 13까지 구간 합을 구한다면 마지막 비트부터 앞으로 이동하며 합 구하기

특정 인덱스 수정

인덱스 트리 구현

#include <stdio.h>
#define NUMBER 7

// 트리 구조로 구간 합 구하기
int tree[NUMBER]; 

// 첫번째 인덱스 부터의 합
int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += tree[i];
        // 마지막 비트만큼 빼면서 앞으로 이동
        i -= (i & -i);
    }
    return res;
}

// 특정 인덱스 수정
void update(int i, int dif) {
    while (i <= NUMBER) {
        tree[i] += dif;
        // 마지막 비트만큼 더하면서 뒤로 이동
        i += (i & -i);
    }
}

// 구간 합 구하기
int getSection(int start, int end) {
    return sum(end) - sum(start - 1);
}

// main
int main(void) {
    update(1, 7);
    update(2, 1);
    update(3, 9);
    update(4, 5);
    update(5, 6);
    update(6, 4);
    update(7, 1);
    printf("1부터 7까지 구간 합 : %d\n", getSection(1, 7));
    
    printf("인덱스 6의 원소를 +3만큼 수정\n");
    update(6, 3);

    printf("4부터 7까지 구간 합 : %d\n", getSection(4, 7));

    system("pause");
    return 0;
}