펜윅트리(Fenwick Tree)

BIT(Binary Indexed Tree)라고도 한다.

O(lgN)에 0부터 해당하는 인덱스까지의 부분합 ( 또는 점차 누적되는 정보 )을 알 수 있다.
기존에 쉽게 사용하는 부분합 배열 (단순히 0~N까지의 합을 각각의 배열 N인덱스에 저장)
은 O(1)에 부분합을 구할 수 있지만 이 경우 한번 모든 부분합을 구해놓고 나서 중간에 값을 갱신할때 다시 O(N)의 갱신이 필요하다. 하지만 펜윅트리는 이를 O(lgN)에 할 수 있게 해준다.

자세한것은 탑코더 튜토리얼 참고
http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/binary-indexed-trees/#add

소스코드는 '프로그래밍 대회에서 배우는 알고리즘 문제해결전략2 - 구종만'에 나온 소스코드를 참고하였다.

#include <cstdio>
#include <vector>
using namespace std;
struct FenwickTree{
    vector<int> tree;
    FenwickTree(int n) : tree(n+1){}
    int sum(int pos){
        ++pos;
        int ret = 0;
        while(pos>0){
            ret+=tree[pos];
            pos&=(pos-1);
        }
        return ret;
    }
    void add(int pos, int val){
        ++pos;
        while(pos<tree.size()){
            tree[pos]+=val;
            pos+=(pos & -pos);
        }
    }
};
int main(){
    FenwickTree ft(10);
    ft.add(0,3);
    ft.add(1,5);
    ft.add(2,2);
    printf("%d",ft.sum(2));

}