This simulator visualizes an 8-element Fenwick tree, showing how a single update ripples through only a few slots and how a prefix-sum query pulls together only a few partial sums to reach the answer.
Click an array position to update its value and watch which tree slots light up, or click a query position to see the log n chain of slots it visits to compute the running total.
Toggle between update mode and query mode, then click array positions to see the affected Fenwick tree slots highlighted with the propagation path.
Every index's lowest set bit is a power of two, so the number of slots touched during an update or query is bounded by the number of bits in the array size, which is why even a billion-element Fenwick tree needs at most about 30 steps.
This simulator visualizes an 8-element Fenwick tree, showing how a single update ripples through only a few slots and how a prefix-sum query pulls together only a few partial sums to reach the answer.
This simulator visualizes an 8-element Fenwick tree, showing how a single update ripples through only a few slots and how a prefix-sum query pulls together only a few partial sums to reach the answer.
Click an array position to update its value and watch which tree slots light up, or click a query position to see the log n chain of slots it visits to compute the running total.
Every index's lowest set bit is a power of two, so the number of slots touched during an update or query is bounded by the number of bits in the array size, which is why even a billion-element Fenwick tree needs at most about 30 steps.