펜윅트리

//펜윅 트리의 완전한 구현
 
//펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을
//빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 
//원소가 전부 0이라고 생각한다
 
struct FenwickTree
{
    vector<int> tree;
    FenwickTree(int n) : tree(n+1) {}
    //A[0...pos]의 부분 합을 구한다.
    int sum(int pos)
    {
        //인덱스가 1부터 시작한다고 생각하자.
        ++pos;
        int ret = 0;
        while(pos > 0)
        {
            ret += tree[pos];
            //다음 구간을 찾기 위해 최종 비트를 지운다.                        
            pos &= (pos-1);
        }
        return ret;
    }
    //A[pos]에 val을 더한다
    void add(int pos, int val)
    {
        //인덱스가 1부터 시작한다고 생각하자.
        ++pos;
        while(pos < tree.size())
        {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};

 

 

 

 

 

 

펜윅트리

부분 합을 이용해 구간 합을 구하는 트리

박스 안의 숫자는 index이고, 밑의 조그만 숫자는 해당 index를 2진수로 표현한 것입니다.

tree[i] : 위 그림에서 index가 i인 부분의 합

 

가상의 A[] 배열의 구간합 [0...pos]를 구하기 위해선

pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종 비트를 계속지워 나가며 구해지는 박스들을 모두 더하면 됩니다.(pos + 1은 1번부터 시작하기 때문입니다.)

 

펜윅트리를 갱신하기 위해선

pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종비트를 계속 더해 만나는 박스들에 새로운 값을 갱신해 주면 됩니다.

 

 

 

 

 

 

시간복잡도

sum : O(lgn)

add : O(lgn)

 

 

 

 

 

 

종만북2