A dart thrown into the dark abstract landed on the Binary Indexed Tree — a flat array that answers prefix sums and takes point updates in O(log n), with no pointers and no tree nodes. The whole engine is one trick: i & (-i) isolates the lowest set bit and tells each index exactly how far to jump. We show the technique live, credit who actually made it, and ask what I-13 should learn — a language that owns neither an array nor a single bit operator.
THE TECHNIQUE low-set-bit · jump the implicit tree
Store partial sums in a flat array bit[1..n]. Cell i is responsible for the block ending at i whose length is lsb(i) = i & (-i). To update index i, add the delta and jump up: i += i & -i. To query the prefix sum 1..i, add cells while jumping down: i -= i & -i. Each jump clears one set bit, so both walks finish in at most log₂n steps. live demo
lsb(i) = i & (-i) // isolate lowest set bit
update(i,d) : while i<=n: bit[i]+=d; i += lsb(i) // walk UP
query(i) : s=0; while i>0: s+=bit[i]; i -= lsb(i) // walk DOWN
return s // = sum of a[1..i]
the tree — bit[i] over indices 1..16 (index in binary; block it covers)
the underlying array a[i] — the truth the tree tracks
Fields are (index i, delta d). Up path glows orange, down path glows cyan. Every query is checked against a brute-force sum of a[] — they must match.
HISTORY & CREDIT credit where it is due
Nearly everyone calls it the Fenwick tree and stops there — but Fenwick invented it is not the whole truth. He named-and-popularised it; the structure was published five years earlier, by someone else, for a different purpose. Here is the honest chain. cited
1989 · Boris Ryabko — publishes the structure in “A fast on-line code” (Soviet Math. Dokl. 39(3):533–537), with a further refinement in 1992 (“A fast on-line adaptive code”, IEEE Trans. Inf. Theory). The real prior inventor. 1994 · Peter M. Fenwick — “A new data structure for cumulative frequency tables” (Software: Practice and Experience 24(3):327–336). Independently described it for arithmetic-coding frequency tables; his framing is where it caught on, so his name stuck to it — the “Binary Indexed Tree.”
So: the name is Fenwick’s (1994), but the structure is Ryabko’s (1989/1992). Both arrived at it independently, in coding theory, before it was a competitive-programming staple. What is open: as with most low-bit array tricks, whether it was folklore among earlier coding-theory practitioners is hard to pin — the two published sources above are the firm ground. open
RECOMMEND FOR I-13 no bits, no array — two walls at once
The Fenwick tree stands on exactly two things I-13 does not have: (a) a bitwise operator — the entire method isi & (-i) — and (b) an indexable array to store bit[] and a[]. I did not assume the gaps; I ran the live compiler and it refused both — proven, not asserted:
i13 check bitand.i13 => bitand.i13:3:10 E0001 unexpected character `&` (a & b: NO bitwise AND — the lsb trick is dead on arrival)
i13 check shift.i13 => shift.i13:2:11 E0102 expected expression (a >> 1: NO shift; > parses as compare, the 2nd > has no operand)
i13 check arr.i13 => arr.i13:2:9 E0001 unexpected character `[` (a[0]: NO array / no indexing — nowhere to store bit[])
i13 run arith.i13 => c = 20 · d = 96 (only + - * / on f64 work; the counted alphabet has no BinOp for bits)
This dart stacks two of I-13’s recurring walls — the bitwise wall (shared with the fast-inverse-square-root dart) and the aggregate wall (nowhere to put an array). Fixing one is not enough; the Fenwick tree needs both.
Recommend (1) — bitwise ops as new BinOp discriminants. Add &, |, ^, <<, >> to the operator table as extra BinOp discriminants. This spends zero new alphabet symbols — the counted 13 stay 13; only the operator enum grows — and it is the same cheap move the other darts proposed for %. That alone makes i & -i expressible.
Recommend (2) — an aggregate story, which is the bigger ask. I-13 has no array, no index, no heap: Constant is a lone f64 and there is no Subscript in THE TWELVE. A Fenwick tree cannot exist without somewhere to hold n cells. The honest options, cheapest first: a fixed-length indexable aggregate reachable through the already-declared-but-unused Attribute node (rank-3 symbol, currently a VM no-op — give it real subscript semantics), or a genuine array type. The first reuses a counted symbol; the second adds real surface.
Tradeoff (stated plainly): I-13’s identity is a counted 13-symbol alphabet and an f64-only scalar core. Bit-ops are nearly free (operator discriminants, no new symbol); the array is not free — it is a new kind of value, and it pushes against the “every value is a scalar” purity. So the honest verdict is asymmetric: add the bit operators now (cheap, and unlocks a whole family of low-bit tricks), and treat the aggregate as a deliberate scope decision — worth it only if data-structure work is meant to live in the galaxy at all.