# Fancy Coder

share my projects and discoveries

## Binary Indexed Tree

Binary Indexed Tree (also called Fenwick tree), a good tutorial is available here

Binary indexed tree’s logical structure is an integer array. Initially array is filled with 0. Binary Indexed Tree allows you to update value of element in array, and compute sum of elements in any index interval. All operations are O(log n).

The implementation is simple and efficient, although quite tricky, and it is very popular in programming contests. Source code follows.

//index from 1 to N
template<size_t N>
class BinaryIndexedTree{
int *a;
int low_bit(int x){return x & -x;}
public:
// i \in [1,N]
while(i<=N){
a[i]+=k;
i+=low_bit(i);
}
}
// i \in [0,N]
int sum(int i){
int res=0;
while(i){
res+=a[i];
i-=low_bit(i);
}
return res;
}
// i \in [0,N], j \in [i,N]
int rangeSum(int i,int j){
return sum(j)-sum(i-1);
}
BinaryIndexedTree(){
a=new int[N+1];
fill(a,a+N,0);
}
~BinaryIndexedTree(){
delete[] a;
}
};