Binary Indexed Tree

 바이너리 인덱스 트리는 앞의 인덱스 트리, 세그먼트 트리와 비슷하게 주어진 구간에서의 누적합을 쉽게 구할 수 있는 자료구조이며 한 데이터의 갱신에 O(log2(N))의 시간복잡도가 소요됩니다.

 이 트리의 특이한 점은 N개의 데이터를 트리로 구성하기위해 N개의 배열만이 필요하며, 재귀 탐색이 아닌 단순 계산만으로 누적합을 계산하므로 메모리나 속도측면에 상당히 빠르다는 특징이 있습니다.

#define vi vector<int>
struct BIT{
        vi v;
    	// 모든 원소가 0 인 size크기의 BIT 생성
    	BIT(int n) : v(vi(n+1)){}
    	// idx는 모두 1-based
    	int read(int idx){
            	int sum = 0 ;
            	while(idx > 0){
                    	sum += v[idx];
                    	idx -= (idx & - idx);
            	}
            	return sum;
    	}
    	// idx 번째의 값에 val을 더함
    	void update(int idx ,int val){
            	while (idx < v.size()){
                    	v[idx] += val;
                    	idx += (idx & -idx);
            	}
    	}
    	// [l, r] 의 구간합
    	int range_sum(int l,int r){
            	return read(r) - read(l-1);
    	}
};