# 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 time.
Changing value of any single element needs 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 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 in the index i.

## Example for responsibility[edit]

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...

## Sample C++ Implementation[edit]

#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; } };

## References[edit]

- 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. |