[c++] 이진 인덱스 트리(Binary Indexed Tree) 데이터 구조

08 Dec 2023

이진 인덱스 트리(Binary Indexed Tree)는 효율적으로 구간 합을 계산하는 데 사용되는 데이터 구조입니다. 주로 배열의 각 요소들의 값을 변경하고 구간 합을 계산하는 연산이 반복되는 경우에 활용됩니다.

이진 인덱스 트리의 작동 원리는 무엇인가요?

이진 인덱스 트리는 각 노드가 특정 인덱스 범위에 대한 합을 저장하며, 구간 합을 계산하는 데 사용됩니다. 각 노드의 값은 구간의 시작부터 현재 인덱스까지의 요소 합을 나타냅니다. 따라서 구간 합을 계산하기 위해서는 여러 노드 값을 합산하여 구간 합을 얻을 수 있습니다.

예를 들어, 인덱스 6의 노드의 값은 인덱스 5와 6에 있는 요소의 합을 나타내고, 인덱스 7의 노드의 값은 인덱스 1부터 7까지의 요소 합을 나타냅니다. 이러한 구조를 통해 각 노드를 거쳐가면서 구간 합을 계산할 수 있습니다.

이진 인덱스 트리의 구현 및 활용 예제

#include <iostream>
#include <vector>

using namespace std;

class BinaryIndexedTree {
public:
    vector<int> BIT;
    int n;

    BinaryIndexedTree(int size) {
        n = size;
        BIT.assign(n+1, 0);
    }

    void update(int index, int val) {
        while (index <= n) {
            BIT[index] += val;
            index += (index & -index);
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += BIT[index];
            index -= (index & -index);
        }
        return sum;
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    BinaryIndexedTree bit(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        bit.update(i+1, arr[i]);
    }
    cout << "Sum of elements in arr[0..2] is " << bit.query(3) << endl;
    cout << "Sum of elements in arr[2..4] is " << bit.query(5) - bit.query(2 - 1) << endl;
    return 0;
}

위의 예제는 C++로 작성된 이진 인덱스 트리의 구현과 활용 예제입니다. 배열의 각 요소를 변경하고, 구간 합을 계산하는 과정이 나타나 있습니다.

결론

이진 인덱스 트리는 각 노드가 특정 인덱스 범위에 대한 합을 저장하여 구간 합을 효율적으로 계산하는 데 사용되는 데이터 구조입니다. 이를 통해 배열 요소의 값을 변경하고 구간 합을 빠르게 계산할 수 있습니다.