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