펜윅트리(fenwick tree), 바이너리인덱스트리(BIT ; Binary Indexed Tree)

펜윅트리란? 

특정 구간, 구간합을 구할 때 빠르게 구할 수 있는 트리이다. 

펜윅트리(Fen Wick Tree) 또는 BIT (Binary Indexed Tree) 바이너리 인덱스 트리 라 부르기도 한다. 

특정 구간의 합을 구할 수 있는데 시작은 1번째 값부터 n번째 값까지 구할 수 있다. 

 

 

그러면 a번째 값부터 b번째 값까지 구하려면 ? [1,b] 번째 값까지 합 - [1,a-1] 번째 값까지 합을 빼게 되면 구할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
 
class BIT{
public:
    typedef long long dtype;
    int S; // size
    vector<dtype> T; // T ; tree
    vector<dtype> A; // A ; Array
 
    BIT(int n): S(n), T(n+1), A(n+1, 0) {}
 
    // p is index;
    // v is A[p] = v;
    void update (int p , dtype v){
        int pivot = p;
        while ( p <= S ){
            T[p] -= A[pivot];
            T[p] += v;
            p += p&(-p);
        }
        A[pivot] = v;
    }
 
    // sum from 1 to p index
    dtype sum ( int p ){
        dtype ret = 0;
        while ( p > 0 ){
            ret += T[p];
            p -= p & (-p);
        }
        return ret;
    }    
 
    void array_print(){
        for(int i = 1 ; i <= S ;i++) printf("Array[%d] : %lld\n",i, A[i]);
        for(int i = 1 ; i <= S ;i++) printf("BIT[%d] : %lld\n",i, T[i]);
    }
};
 

먼저 코드를 보면, BIT 클래스를 만들었다. 

1) class 변수, 그리고 생성자를 설명

2) update 메소드 설명

3) sum 메소드 설명 

순서로 설명을 한다. 

1) class 변수 , 생성자

class BIT{
public:
    typedef long long dtype;
    int S; // size
    vector<dtype> T; // T ; tree
    vector<dtype> A; // A ; Array
 
    BIT(int n): S(n), T(n+1), A(n+1, 0) {}
 
    // p is index;
    // v is A[p] = v;
    void update (int p , dtype v){
        // pass
    }
 
    // sum from 1 to p index
    dtype sum ( int p ){
        // pass
    }    
};
 

1) class 변수 , 생성자 

S는 사이즈를 뜻한다. 즉 트리의 크기, 그리고 배열의 크기를 저장한다. 

T는 BIT 트리를 뜻한다. 0번째 인덱스를 사용하지 않으므로 n+1 로 [0...n] 크기의 배열을 만들어야 한다.

A는 각 인덱스 마다 값을 저장한다. 이 또한 0번째 인덱스를 사용하지 않으므로 n+1 로 [0...n] 크기의 배열을 만들어야 한다.

이때 BIT는 0번째 인덱스는 사용하지 않는다. 1번째 인덱스부터 사용한다. 그 이유는 각 구간합을 저장, 계산할 때 

(-) 값으로 보수를 취하고 각 비트를 AND(&) 연산으로 곱하여 다음 인덱스 위치로 이동하여 저장된 구간합을 구하거나, 업데이트 할 수 있기 때문이다. 

예를 들어, 총 9개 수열이 있고, 순서대로 1,2,3... ,9 까지 있다고 했을 때 A (Array) 와 T (BIT) 는 아래와 같이 표현할 수 있다.

2) update 메소드 설명

#include<cstdio>
#include<vector>
using namespace std;
 
class BIT{
public:
    typedef long long dtype;
    int S; // size
    vector<dtype> T; // T ; tree
    vector<dtype> A; // A ; Array
 
    BIT(int n): S(n), T(n+1), A(n+1, 0) {}
 
    // p is index;
    // v is A[p] = v;
    void update (int p , dtype v){
        int pivot = p;
        while ( p <= S ){
            T[p] -= A[pivot];
            T[p] += v;
            p += p&(-p);
        }
        A[pivot] = v;
    }
 
    // sum from 1 to p index
    dtype sum ( int p ){
        // pass
    }    
};

위 그림의 설명을 이제 코드로 보면...

update(index, index_value) 로 표현한다. 

update 메소드의 사용은 

void update (int p , dtype v){
    int pivot = p; // (2)
 
    while ( p <= S ){ // (1)
        T[p] -= A[pivot];
        T[p] += v;
        p += p&(-p);
    }
 
    A[pivot] = v; // (2)
}

(1) T ( BIT ) 에 Array 에 index 값이 포함된 구간합을 저장한 T[n] 을 업데이트 하고, 

T[p] -= A[pivot]; 을 빼주는 이유는 

이전에 저장된 배열 인덱스 값 (A[pivot])을 빼고, 

T[p] += v;

새로 업데이트 하려는 값 (v) 를 다시 더해주기 위해서 이다. 

p += p & (-p); pivot을 포함한 BIT의 인덱스 위치구하고 더해주는 역할을 한다. 

p & (-p) ; // LSB(least significant bit) 최하위 비트가 1이 되는 위치를 구할 수 있다.

(2) A ( Array )에 index 에 위치한 값을 index_value 로 업데이트 한다. : A[index] = index_value

int pivot = p 를 하는 이유는 BIT가 모두 업데이트 되기 전까지는 이전 A[index] 값을 사용해야하기 때문이다. 

(1) 과정이 끝난 후 A[pivot] 값을 업데이트 한다.

 

(1), (2) 과정이 끝나면 BIT와 Array 를 모두 업데이트가 완료된다. 

3) sum 메소드 설명

// sum from 1 to p index
dtype sum ( int p ){
    dtype ret = 0;
    while ( p > 0 ){
        ret += T[p];
        p -= p & (-p);
    }
    return ret;
}    

sum (p) 메소드는 

1 부터 p 까지 합을 모두 구한다. 

p & (-p) ; // LSB(least significant bit) 최하위 비트가 1이 되는 위치를 구할 수 있다.

예-1) sum (8) 로 [1, 8] 까지 인덱스의 합을 구하면

while 문의 첫 시행에서 

ret += T[8];

(여기서 0...0 은 앞 비트가 모두 0임을 뜻한다. 1...1 은 모두 1임을 뜻한다.)

p : 0...0 1000 (2) 

-p: 1...1 1000 (2)

이 값을 & 하게되면

p&(-p): 0...0 1000(2) 인 8이 나오게 된다. 

그러면 T[8] = A[1...8] 을 바로 구한다. 

예-2) sum(7) 로 [1,7] 까지 인덱스 합을 구하면

첫 시행에서 p = 7;

p     : 0...0 0111 (2)

-p    : 1...1 1001 (2)

p&(-p): 0...0 0001 (2) 인 1값이 된다. 

그러면 

p는 p = 6 이 된다. 

ret += T[6]

T[6] 의 값은 A[5,6] 의 합이다. 

이때 다시 계산을 해보면

p     : 0...0 0110 (2)

-p    : 1...1 1010 (2)

p&(-p): 0...0 0010 (2) 로 2값을 가진다. 

그러면 

p는 p = 4 가 되고,

T[4] = A[1,4] 의 합이며, ret += T[4] 를 더한다. 

이때 p -= p&(-p) 를 하게 되면 

p&(-p) = 4 가되고 

p 값은 0이 되어 

ret = T[7] + T[6] + T[4] 를 더해 값을 반환한다. 

각 구간합을 비트 연산을 통해 인덱스를 넣어 줄 수 있다.