# Fenwick tree

From Algorithmist

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

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