# 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 in the index i.

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

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