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
| Syntax | Description |
|---|---|
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
| Method | Signature | Returns | Description |
|---|---|---|---|
add | (index: usize, delta: i32) => void | void | Add delta to the element at index |
sum | (index: usize) => i32 | i32 | Return the sum of the first index elements, that is the range [0, index) |
len | () => usize | usize | Return the number of positions |
isEmpty | () => boolean | boolean | Whether 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
| Operation | Time Complexity |
|---|---|
add | O(log n) |
sum | O(log n) |
len | O(1) |
isEmpty | O(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 + 4Negative 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 + 30len and isEmpty
tyrus
const bit = FenwickTree(0);
print(bit.isEmpty()); // true
print(bit.len()); // 0