Binary Indexed Tree

A Fenwick tree (BIT) answers prefix-sum queries and point updates in O(log n) with O(n) space — simpler to implement than a segment tree. Index arithmetic uses i += i & (-i) to traverse. Use for inversion counting, order statistics, and frequency prefix sums.