Binary Indexed Trees (Fenwick Trees): Mutable Prefix Sums

Concepts: pyFenwickTree, pyBIT, pyMutablePrefixSum

A plain prefix array is amazing when the data is immutable. But the moment you get an update -- 'change arr[i] to v' -- your entire O(n) prefix array is stale, and you must rebuild in O(n). If updates are frequent and interspersed with queries, you need a data structure that handles both in O(log n). That is the Fenwick tree, also called a Binary Indexed Tree (BIT). It is the most elegant data structure in competitive programming, and it appears in senior and staff data engineering interviews because it tests both algorithmic thinking and the ability to reason about index manipulations involving bit arithmetic. When to Reach for a BIT vs. Other Structures If you only need point updates and prefix sums (or range sums via two prefix queries), a BIT is the right tool. It is simpler to impleme