# Fenwick tree

**Fenwick tree** (aka **Binary indexed tree**)
is a data structure that maintains a sequence of elements,
and is able to compute cumulative sum of any range of consecutive elements in *O*(log*n*) time.
Changing value of any single element needs *O*(log*n*) time as well.

The structure is space-efficient in the sense that it needs the same amount of storage as just a simple array of *n* elements.

The basic rule that the structure works on is that, just like a number can be represented as a sum of some powers of two, so can a cumulative sum be represented as a sum of some partial cumulative sums .

Every index in the cumulative sum array, say i, is *responsible* for the cumulative sum from the index i to (i - (1<<r) + 1), where r represents the last 1 bit set int the index i.

## [edit] Example for responsibility

Example: 15 ( 1111 ) is responsible for sums from 15 to (14+1) { 1111 - 0001 +1 } 14 ( 1110 ) is responsible for sums from 14 to (12+1) { 1110 - 0010 + 1 } 12 ( 1100 ) is responsible for sums from 12 to (8+1) { 1100 - 0100 + 1 } .... and so on...

## [edit] Sample C++ Implementation

#include <vector> using namespace std; // In this implementation, the tree is represented by a vector<int>. // Elements are numbered by 0, 1, ..., n-1. // tree[i] is sum of elements with indexes i&(i+1)..i, inclusive. // (Note: this is a bit different from what is proposed in Fenwick's article. // To see why it makes sense, think about the trailing 1's in binary // representation of indexes.) class Fenwick_Tree_Sum { vector<int> tree; Fenwick_Tree_Sum(const vector<int>& Arg)//Arg is our array on which we are going to work { tree.resize(Arg.size()); for(int i = 0 ; i<tree.size(); i++) increase(i, Arg[i]); } // Increases value of i-th element by ''delta''. void increase(int i, int delta) { for (; i < (int)tree.size(); i |= i + 1) tree[i] += delta; } // Returns sum of elements with indexes left..right, inclusive; (zero-based); int getsum(int left, int right) { return sum(right) - sum(left-1); //when left equals 0 the function hopefully returns 0 } int sum(int ind) { int sum = 0; while (ind>=0) { sum += tree[ind]; ind &= ind + 1; ind--; } return sum; } };

## [edit] References

- Peter M. Fenwick. A new data structure for cumulative frequency tables. Software - Practice and Experience, 24(3):327--336, March 1994.
- http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
- http://en.wikipedia.org/wiki/Fenwick_tree

This is a stub or unfinished. Contribute by editing me. |