-
Active Index
-
LSB
0
Running Sum
0
Tree Cell
Ready
Status
Current node in update/query walk
Covered interval for tree[index]
Cells contributing to current prefix sum
Step Log
How It Works
A Fenwick tree stores prefix information in a compact 1-indexed array. Each cell tree[i] covers the range (i - lowbit(i) + 1) ... i.
- Point updates jump upward with
i += lowbit(i). - Prefix queries jump downward with
i -= lowbit(i). - The lowest set bit controls both the covered interval and the traversal path.