FenwickTree

v0.0.11tested

Fenwick (Binary Indexed) tree over an array of non-negative numbers: O(log n) prefix sums, point updates, and monotonic lower-bound search, plus O(n) bulk rebuild. lowerBound assumes all values are non-negative (the prefix function must be non-decreasing)

Source Tests

Example

const tree = new FenwickTree(5);
tree.build([10, 20, 30, 40, 50]);
tree.prefix(3); // 60
tree.update(1, 5); // value at index 1 becomes 25
tree.lowerBound(65); // 3 — largest c with prefix(c) <= 65

Signature

class FenwickTree

Properties

Property	Type	Default	Description
`size`readonly	`number`	—	—

Methods

build

Bulk (re)initialization from raw values, O(n)

build(values: ArrayLike<number>): void

Parameter	Type	Default	Description
`values`	`ArrayLike<number>`	—	The values to load, `values.length` must equal `size`

update

Add delta to the value at index, O(log n)

update(index: number, delta: number): void

Parameter	Type	Default	Description
`index`	`number`	—	Zero-based index of the value to change
`delta`	`number`	—	Amount to add (may be negative)

prefix

Sum of the first count values, O(log n)

prefix(count: number): number

Parameter	Type	Default	Description
`count`	`number`	—	How many leading values to sum

ReturnsnumberThe prefix sum

lowerBound

Largest c in [0, size] with prefix(c) + c * stride <= target, O(log n). stride models a constant per-item addition (e.g. a layout gap) without storing it in the tree

lowerBound(target: number, stride = 0): number

Parameter	Type	Default	Description
`target`	`number`	—	The offset to search for
`stride`?	`number`	`0`	Constant added per item, defaults to `0`

ReturnsnumberThe largest count whose strided prefix does not exceed target