Fenwick tree

From Algorithmist
Jump to: navigation, search

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.

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]


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