Fenwick tree

A Binary Indexed Tree: prefix sums and point updates both in O(log n), demoing the p/moul/x/daily/fenwick library.

The values

3, 1, 4, 1, 5, 9, 2, 6 — 8 slots totalling 31.

Prefix sums

i	value	Prefix(i+1)
0	3	3
1	1	4
2	4	8
3	1	9
4	5	14
5	9	23
6	2	25
7	6	31

Range queries

call	meaning	result
`Range(2, 5)`	slots 2, 3, 4	10
`Range(0, 8)`	everything	31
`Range(5, 5)`	empty	0
`Range(-9, 99)`	clamped to the ends	31

Reads clamp instead of panicking. A realm cannot be redeployed on the same path, so a Render that panics on an out-of-range index is a page that is broken for good. Writes do panic: a bad Add is a transaction, and aborting it is the useful answer.

What the tree actually stores

The array is not a copy of the values. Each internal slot holds the sum of a run of them, and the run lengths are the powers of two in the index. That is the whole trick, and Covers makes it visible.

node	covers slots	sum
1	`[0, 1)`	3
2	`[0, 2)`	4
3	`[2, 3)`	4
4	`[0, 4)`	9
5	`[4, 5)`	5
6	`[4, 6)`	14
7	`[6, 7)`	2
8	`[0, 8)`	31

A prefix walk visits one node per set bit of the index, and those nodes tile the prefix exactly: no gap, no overlap. Eight slots means at most three nodes per query.

The weighted draw

SearchPrefix(target) names the slot that owns a target drawn below Total, in O(log n). Each holder is picked in proportion to their stake, and a zero stake can never be picked at all.

holder	stake	owns targets	share
alice	30	`[0, 30)`	30%
bob	0	none	0%
carol	45	`[30, 75)`	45%
dave	5	`[75, 80)`	5%
erin	20	`[80, 100)`	20%

target	SearchPrefix	holder
0	0	alice
29	0	alice
30	2	carol
74	2	carol
99	4	erin

Note target 30: it is the first one past alice's share, and it skips bob entirely rather than landing on a holder with nothing staked. The search steps over zero-weight slots because their prefix does not advance, not because anything checks for them.

Why not a plain slice

Two obvious implementations each win one column and lose another. A realm whose scoreboard is written by every player and read by every page view pays both costs, which is where the middle row earns its keep.

structure	point update	prefix sum	weighted draw
plain slice	`O(1)`	`O(n)`	`O(n)`
Fenwick tree	`O(log n)`	`O(log n)`	`O(log n)`
running totals	`O(n)`	`O(1)`	`O(log n)`

The tree also carries no storage overhead: it is exactly n values, rearranged.