# Fancy Coder

share my projects and discoveries

## Binary Indexed Tree

April 19, 2011

Posted by on 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] void add(int i,int k=1){ 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; } };

Advertisements