Theory

• TopCoder – Binary Indexed Trees
• Algorithms Live – Fenwick tree
• Wikipedia – Fenwick tree

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

class FenwickTree {
    private:
        vector<int> tree;
        int size;

        int leastOneBit(int idx) {
            return idx & -idx;
        }
    public:
        FenwickTree(int n) {
            size = n + 1;
            tree.resize(size);
        }

        int read(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= leastOneBit(idx);
            }
            return sum;
        }

        void update(int idx, int val) {
            while (idx < size) {
                tree[idx] += val;
                idx += leastOneBit(idx);
            }
        }
};

Practice

• Kattis – Movie collection
• AtCoder – B Fenwick Tree