Fenwick Tree
An array where cell i holds the sum of a range whose length is its lowest set bit.
Result · step 8 of 10Fenwick Tree: Build from eight values
Cell 7 covers 7 to 7 and now holds 2. Its parent is 7 + lowbit(7) = 8, so 2 is folded in there too.
What you will see
Query jumps i -> i minus lowbit(i); update jumps i -> i plus lowbit(i); bits shown alongside.
Cost
| prefix query | O(log n) |
|---|---|
| point update | O(log n) |
| build | O(n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.