Package fenwick is a Binary Indexed Tree (Peter Fenwick, 1994): an array of int64 that answers a prefix sum and appli...
gno.land/p/moul/x/daily/fenwick/v0A Binary Indexed Tree over int64: New, FromSlice, Add, Set, Prefix, Range, At, Total, SearchPrefix, Slice, Covers.
1import "gno.land/p/moul/x/daily/fenwick/v0"
2
3tr := fenwick.FromSlice([]int64{3, 1, 4, 1, 5})
4tr.Prefix(3) // 8 sum of [0, 3)
5tr.Range(1, 4) // 6 sum of [1, 4)
6tr.Add(2, 10) // point update, O(log n)
7tr.SearchPrefix(7) // 2 the slot owning target 7
A realm that keeps a running tally is choosing between two bad options without
noticing. A plain slice updates in O(1) and sums in O(n). A slice of running
totals sums in O(1) and updates in O(n). A scoreboard is written by every
player and read by every page view, so it pays both costs. A Fenwick tree does
both in O(log n), in exactly n values of storage, rearranged.
The operation worth importing a package for is SearchPrefix, not the prefix
sums. Given a target below Total it names the slot that owns it, in O(log n),
by descending the tree rather than scanning it. That is the primitive behind a
stake-weighted draw (pick a number, ask who holds it) and behind a leaderboard's
rank lookup. Prefix sums alone would not justify a data structure.
Three behaviours worth knowing before you use it:
Prefix,
Range, At, Covers and SearchPrefix clamp whatever index they are
handed; Add, Set and New panic. A read is what Render calls, and 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 permanently. A write is a
transaction, where aborting is the useful answer and the caller can still
recover.SearchPrefix. It falls out of the
descent rather than being checked for: a zero does not advance the prefix, so
no target can land on it. That is the property a weighted draw depends on, and
the one a naive "first running total >= target" scan gets wrong.SearchPrefix is only meaningful when every value is non-negative. With a
negative in the tree the prefix sums stop increasing and "the smallest index
whose prefix exceeds the target" stops being well defined. Negative values are
not forbidden, because Add with a negative delta is the ordinary way to
decrement a counter; it is this one method that needs them absent.MaxSize caps construction at 65,536 slots. Queries are O(log n) whatever the
size; the cap is there so the single O(n) operation, building the tree, cannot
be sized from unbounded user input. Sums must fit in int64, which gno does not
check and neither does this package.
Covers(i) reports which slots an internal node summarizes. It is not needed to
use the tree; it exists so the structure can be shown rather than asserted, and
the demo realm renders it.
Live demo: r/moul/x/daily/fenwickdemo.
Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.
🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.
Package fenwick is a Binary Indexed Tree (Peter Fenwick, 1994): an array of int64 that answers a prefix sum and applies a point update in O(log n), with no extra storage beyond the array itself.
The tradeoff it occupies is the whole reason to reach for one. A plain slice updates in O(1) and sums in O(n). A slice of running totals sums in O(1) and updates in O(n). A Fenwick tree does both in O(log n), which is what a realm wants when reads and writes are interleaved: a scoreboard written by every player and read by every render.
The operation that actually justifies the package is Tree.SearchPrefix: the smallest index whose prefix sum exceeds a target, in O(log n), by descending the tree rather than scanning it. That is the primitive behind a stake-weighted draw (pick a number below Total, ask which holder owns it) and behind a leaderboard's rank lookup. Prefix sums on their own would not be worth a data structure.
Reads are total and writes are strict, deliberately: see the package README.
A live demo of this package is at r/moul/x/daily/fenwickdemo(/r/moul/x/daily/fenwickdemo/v0).
MaxSize bounds the number of slots so a caller cannot size the tree from unbounded user input and make the allocation itself the attack. It is not a gas figure: a query costs O(log n) regardless, and the cap exists so the one O(n) operation in the package, construction, stays bounded.
FromSlice returns a Tree holding vals, built in O(n) rather than by n successive Add calls, which would cost O(n log n).
The slice is copied; later writes to vals do not reach the tree.
New returns a Tree of n zero-valued slots.
It panics if n is negative or above MaxSize: both are programmer errors that a caller cannot recover from, and a silently clamped size would hand back a tree that disagrees with the caller about its own length.
Tree is a Binary Indexed Tree over int64 values, addressed 0-based.
The zero value is not usable; build one with New or FromSlice.
Add adds delta to the value at i.
It panics if i is out of range. A write is a transaction: failing loudly is the correct outcome, and the caller still has the chance to abort.
At returns the value at i, or 0 if i is out of range. Total, like the other reads.
Covers returns the half-open range [lo, hi) of 0-based slots that the internal node at 1-based position i summarizes, which is what makes the structure legible rather than magic. It is exported for the demo and for anyone trying to see the shape; it is not needed to use the tree.
It returns (0, 0) when i is outside [1, Len].
Len returns the number of slots.
Prefix returns the sum of the first i values, that is of [0, i).
It is total: i is clamped into [0, Len], so Prefix(-5) is 0 and Prefix(1e9) is Total. Reads are what Render calls, and a panicking Render is a page that can never be displayed again, on a path that can never be redeployed.
Range returns the sum of [lo, hi). It is total: bounds are clamped, and an empty or inverted range is 0.
SearchPrefix returns the smallest index i for which Prefix(i+1) > target, or Len if no prefix exceeds it. It runs in O(log n) by descending the tree.
With non-negative values this is the weighted select: draw a target in [0, Total) and SearchPrefix names the slot that owns it, each slot chosen in proportion to its value. A zero-valued slot can never be selected, which is the property that makes it usable for a stake-weighted draw.
It is total, and a negative target returns 0.
The result is only meaningful when every value is non-negative: with a negative value in the tree the prefix sums stop increasing and "the smallest index whose prefix exceeds target" stops being well defined. The package does not forbid negative values, because Add with a negative delta is the ordinary way to decrement a counter; it is SearchPrefix alone that needs them absent.
Set replaces the value at i, returning the value it displaced.
It panics if i is out of range, for the same reason Tree.Add does.
Slice materializes the tree back into a plain slice, in O(n log n).
It exists for rendering and for tests. A hot path should not call it.
Total returns the sum of every value.
