If you need prefix sums but the array keeps changing, a Binary Indexed Tree (BIT) gives you both updates and queries in O(log n). It's the fastest, simplest structure for dynamic range sums. This post breaks down what BITs are, how they work under the hood, and why they're the go-to choice when a static prefix sum array isn't enough.
What is a Binary Indexed Tree?
A Binary Indexed Tree (also called a Fenwick Tree) is a data structure that supports two operations efficiently:
- Point update — add a value to a specific index