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(logn) time. Changing value of any single element needs O(logn) 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


This is a stub or unfinished. Contribute by editing me.
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox