func NewTree
NewTree returns an empty tree.
fenwick source pure
Package fenwick is an order-statistic Fenwick (binary indexed) tree over non-negative int64 weights, backed by avl.Tr...
Package fenwick is an order-statistic Fenwick (binary indexed) tree over non-negative int64 weights, backed by avl.Tree so it can live in realm state.
It exists to answer one question in O(log N): given a random unit k drawn from [0, Total()), which index owns that unit? That is the weighted-raffle draw — each index's value is its ticket count, and Select maps a ticket number to its owner. The naive version of that answer walks every index accumulating values until the running total passes k, which is O(N) and will eventually exceed a block's gas limit. Select never walks: it descends the tree's binary structure, touching at most ~log2(N) nodes.
DESIGN DECISION — negative deltas are rejected, not supported. Add panics on a negative delta and Append panics on a negative initial value. This structure is append-and-grow only. The reason is that Select is only meaningful while prefix sums are monotonically non-decreasing: with a negative value somewhere, "the index owning unit k" is not well defined and the binary descent would silently return a wrong owner rather than fail. Refusing the input loudly is the only honest option, so a caller that needs decreasing weights gets a panic instead of a corrupt draw. The rest of the structure (Add, Append, Total, ValueAt, Len) is otherwise a general, reusable Fenwick tree.
Complexity: Append O(log N), Add O(log N), Select O(log N), Total O(1), ValueAt O(log N) (one avl lookup), Len O(1).
1
1
type Tree
structTree is an order-statistic Fenwick tree.
Storage is two avl.Trees keyed by index (never a Go map or a slice, so that realm state stays deterministic and persistent):
- values holds the caller-visible value at each 0-based index.
- nodes holds the Fenwick partial sums, keyed by 1-based position, where node j covers the value range (j-lsb(j), j].
total is maintained incrementally so Total is O(1).
Methods on Tree
func Add
method on TreeAdd increases the value at index i by delta. i must be in [0, Len()). Panics on a negative delta: this structure is append-and-grow only, and silently accepting a decrease would make Select return wrong owners rather than fail (see the package doc). A zero delta is accepted and is a no-op.
func Append
method on TreeAppend adds a new index at the end with the given initial value and returns its 0-based index. Panics if value is negative: see the append-and-grow note in the package doc.
func Len
method on TreeLen returns the number of indices.
func Prefix
method on TreePrefix returns the sum of values at indices [0, i). Panics if i is outside [0, Len()]. O(log N).
func Select
method on TreeSelect returns the index owning cumulative unit k, that is the unique i with Prefix(i) <= k < Prefix(i+1). Panics if k is outside [0, Total()). O(log N): a binary descent over the tree's node positions, never a walk over indices.
An index whose value is 0 owns no units and is therefore never returned: the descent takes the largest position whose prefix is still <= k, which steps past any zero-valued index.
func Total
method on TreeTotal returns the sum of all values. O(1).
func ValueAt
method on TreeValueAt returns the value stored at index i. Panics if i is out of range.
Imports 3
/p/g1r4aw43kagaaquhegxw6xr346h9f2qu2ezf0jar/fenwick
