Skip to content

FenwickTree ​

FenwickTree implements a Fenwick tree (binary indexed tree) over a fixed-size array of 32-bit integers, supporting prefix sums and point updates in O(log n).

Construction ​

SyntaxDescription
FenwickTree(n)Create a tree over n zero-initialized positions

Positions are zero-indexed from 0 to n - 1. The length n may be zero.

Methods ​

MethodSignatureReturnsDescription
add(index: usize, delta: i32) => voidvoidAdd delta to the element at index
sum(index: usize) => i32i32Return the sum of the first index elements, that is the range [0, index)
len() => usizeusizeReturn the number of positions
isEmpty() => booleanbooleanWhether the tree has no positions

sum(index) returns the sum of the first index elements (exclusive upper bound): sum(0) is 0 and sum(n) is the total over all positions. add aborts with a runtime error when index >= n; sum aborts when index > n.

Complexity ​

OperationTime Complexity
addO(log n)
sumO(log n)
lenO(1)
isEmptyO(1)

Examples ​

Construction ​

tyrus
import { FenwickTree } from "tyrus:algorithm";

const bit = FenwickTree(6);

add ​

tyrus
const bit = FenwickTree(4);

bit.add(0, 1);
bit.add(1, 2);
bit.add(2, 3);
bit.add(3, 4);

sum ​

tyrus
const bit = FenwickTree(4);

bit.add(0, 1);
bit.add(1, 2);
bit.add(2, 3);
bit.add(3, 4);

print(bit.sum(0));  // 0
print(bit.sum(1));  // 1
print(bit.sum(3));  // 1 + 2 + 3
print(bit.sum(4));  // 1 + 2 + 3 + 4

Negative deltas ​

tyrus
const bit = FenwickTree(3);

bit.add(0, 10);
bit.add(1, 20);
bit.add(2, 30);

bit.add(1, -5);

print(bit.sum(2));  // 10 + 15
print(bit.sum(3));  // 10 + 15 + 30

len and isEmpty ​

tyrus
const bit = FenwickTree(0);

print(bit.isEmpty());  // true
print(bit.len());      // 0