Binary Indexed Tree (BIT,펜윅 트리)

Binary Indexed Tree(BIT)

N을 배열의 size라 하자.

배열에서 i 번째 원소부터 j 번째 (i<j) 원소까지의 합을 구한다고 해보자.

naive하게 더하면 O(N) 이 걸린다.

추가적인(auxiliary) space를 사용하여 S[i]를 0 번째 부터 i-1번째 까지의 합으로 정의하면,

S[i] = S[i-1] + A[i-1] 를 통해 S를 O(N) 을 통해 구할 수 있고

i 번째 원소부터 j번째 합은 다음과 같이 O(1)에 구할 수 있다.

$\sum_{k=i}^{j}A[k] = S[j]-S[i-1]$

하지만 만약 도중에 배열 값이 바뀐다고 가정하면 이를 update하는데 다시 O(N) 이 걸린다.

SUM : 원소의 합 구하기, 혹은 i번째에서 j까지의 어떤 연산. ADD : 어떤 특정 원소의 값이 수정, 더해지거나 등등..

요약하자면,

이 두가지 연산 SUM과 ADD에 대해 앞서 설명한 일반적인

자료구조를 사용할 경우 각각 O(N)이 걸리는 경우가 발생한다.

저 연산들을 N번 사용해야 한다면 최종적으로 O(N^2) 이 걸릴 것이다.

이 경우 Binary Indexed Tree를 사용하면 각 두가지 연산을 O(log N)에 해결하여 이득을 볼 수 있다.

Binary Indexed Tree에 대한 설명은 다음 Youtube 링크에 자세히 설명되어 있다.

Click This Link

구현은 앞서 설명한 S를 이용하고 인덱스를 찾아가는 방법을 이해하면,

혹은 외워두면 쉽게 사용할 수 있을 것 같다.

Tip & Motivation

---

• 모든 자연수 n은 2의 거듭제곱의 합으로 나타낼 수 있다. (ex, 14 = 8 + 4 + 2, 5 = 4 + 1)
• last-set bit(가장 오른쪽에 있는 1) 을 구하는 식 : x &(-x)
  
  

Code

---

void Add(vector<int>& H, int pos,int val){
    while(pos<=Max){
        H[pos]+= val;
        pos += pos&(-pos);
    }
    return;
}

int Sum(vector<int> &H, int pos){
    int tmp = 0;
    while(pos>0){
        tmp += H[pos];
        pos -= pos&(-pos);
    }
    return tmp;
}

적용할 수 있는 문제

---

hackerrank에서 문제를 풀다가 알게되었다.

난이도는 hard 이다.

하지만 이 자료구조를 알고있다면 쉽게 풀 수 있을 것이다.

도전하기