Fenwick tree

From Algorithmist

Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

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.
// (this is a bit different from what is proposed in Fenwick's article.)

// Creates a zero-initialized Fenwick tree for n elements.
vector<int> create(int n) { return vector<int>(n, 0); }

// Returns sum of elements with indexes a..b, inclusive
int query(const vector<int> &tree, int a, int b) {
    if (a == 0) {
        int sum = 0;
        for (; b >= 0; b = (b & (b + 1)) - 1)
          sum += tree[b];
        return sum; 
    } else {
        return query(tree, 0, b) - query(tree, 0, a-1);
    }
}

// Increases value of k-th element by inc.
void increase(vector<int> &tree, int k, int inc) {
    for (; k < (int)tree.size(); k |= k + 1) tree[k] += inc;
}

[edit] References

Retrieved from "http://www.algorithmist.com/index.php/Fenwick_tree"
Personal tools