Struct FenwickTree 

pub struct FenwickTree { /* private fields */ }

Fenwick tree (Binary Indexed Tree) for prefix sum queries over u32 values.

Designed for virtualized list height layout: each entry i stores the height of item i, and prefix(i) gives the y-offset of item i+1.

Implementations

impl FenwickTree

pub fn new(n: usize) -> Self

Create a Fenwick tree of size n initialised to all zeros.

pub fn from_values(values: &[u32]) -> Self

Create a Fenwick tree from an initial array of values in O(n).

This is faster than calling update n times (which would be O(n log n)).

pub fn len(&self) -> usize

Number of elements.

pub fn is_empty(&self) -> bool

Whether the tree is empty.

pub fn update(&mut self, i: usize, delta: i32)

Add delta to element at position i (0-indexed). O(log n), zero alloc.

Panics

Panics if i >= n.

pub fn set(&mut self, i: usize, value: u32)

Set element at position i to value (0-indexed). O(log n).

pub fn get(&self, i: usize) -> u32

Get the value at position i (0-indexed). O(log n).

Computed as prefix(i) - prefix(i-1).

pub fn prefix(&self, i: usize) -> u32

Prefix sum of elements [0..=i] (0-indexed). O(log n), zero alloc.

Panics

Panics if i >= n.

pub fn range(&self, left: usize, right: usize) -> u32

Range sum of elements [left..=right] (0-indexed). O(log n).

Panics

Panics if left > right or right >= n.

pub fn total(&self) -> u32

Total sum of all elements. O(log n).

pub fn batch_update(&mut self, deltas: &[(usize, i32)])

Apply multiple updates in a single pass. O(m log n), zero alloc.

Each (index, delta) pair is applied sequentially. This produces identical results to calling update for each pair individually.

pub fn rebuild(&mut self, values: &[u32])

Rebuild the tree from a fresh array of values in O(n).

Requires values.len() == self.n.

Panics

Panics if values.len() != self.n.

pub fn find_prefix(&self, target: u32) -> Option<usize>

Find the largest index i such that prefix(i) <= target.

Returns None if all prefix sums exceed target (i.e., values[0] > target). This is useful for binary-search-by-offset in virtualized lists. O(log n), zero alloc.

pub fn resize(&mut self, new_n: usize)

Resize the tree. If growing, new elements are initialised to 0. If shrinking, excess elements are dropped. O(new_n).

Trait Implementations

impl Clone for FenwickTree

fn clone(&self) -> FenwickTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for FenwickTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.