Fenwick Trees

Binary Indexed Trees · Prefix Sums

1:00

How a single bit trick — isolating the lowest set bit with i & -i — makes both point updates and prefix-sum queries run in O(log n) on a mutable array.

By the end, you can

Explain why neither a plain array nor a prefix-sum array satisfies both O(fast) update and O(fast) query.
Derive `i & -i` from two's complement arithmetic and state what it isolates.
Determine the responsibility range (start index and length) of any BIT slot given its index.
Trace the update walk for a given index and count how many slots are modified.
Trace the prefix-query walk for a given index and identify the disjoint blocks accumulated.
Compute a range sum as the difference of two prefix queries.
State the time and space complexity of BIT build, update, and query.
Identify which aggregation operations (sum, XOR vs. min/max) are compatible with a Fenwick tree and explain why.

Up next in String Algorithms, Advanced DP & Competitive Techniques