바이너리 인덱스 트리는 앞의 인덱스 트리, 세그먼트 트리와 비슷하게 주어진 구간에서의 누적합을 쉽게 구할 수 있는 자료구조이며 한 데이터의 갱신에 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); } };