Fenwick Tree
Algorithms & Data
A Fenwick tree (binary-indexed tree) keeps
a running total you can update one bin at a time and query over any range in a handful of
steps — using one clever trick: i & -i isolates a number's lowest set bit, and that
drives a hop up and down a virtual tree of partial sums. Here a moving bump feeds the tree and its
integral — the running prefix sum — rises as a staircase beneath it. Runs on its own; no
joypad needed. Written in C and compiled with the
llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — the signal moves; its running integral reshapes below.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
Keeping a running sum that you can both update and slice cheaply is a common need — leaderboards, histograms, cumulative distributions. The Fenwick tree does it with two tiny loops:
update(i, delta): for (; i <= n; i += i & -i) tree[i] += delta; query(i): for (s = 0; i > 0; i -= i & -i) s += tree[i]; // i & -i isolates the lowest set bit — the whole trick
Every hop adds or removes the lowest set bit of the index, walking a tree that only exists implicitly in the bit pattern. The demo integrates a moving signal — the amber staircase is the running sum of the green bars — and stays bit-exact across every codegen mode.
Compiler stress-test
| Item | What it exercises |
|---|---|
| i & -i | Masking a number with its two's-complement negation isolates its lowest set bit. A binary-indexed tree uses that to hop up (add the low bit) and down (subtract it) a virtual tree of partial sums — a bit-twiddling idiom no earlier demo emits. |
| prefix sums in log time | A Fenwick tree keeps a running total that supports both updating a single bin and asking for the sum of a range in about log-n steps — far fewer than re-adding everything. Here it maintains the "integral" of a live signal. |
| width-safe negation | The low bit is computed as (uint16)(i & (uint16)(0u - i)) so the two's-complement wraps at 16 bits identically on the host (32-bit int) and the 65816 (16-bit int) — a subtlety that matters for a bit-exact differential. |
| cross-checked | The build gate compares the tree's prefix sums against a plain linear sum of the same bins; they must match exactly, so a wrong i & -i walk is caught immediately. |
Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg
(and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build
gate's WRAM assert (gate CRC 0x3454 — a fold of prefix and range sums, each
cross-checked against a linear reference) live in this tab. No far pointers — the same source
passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg,
-verify clean.