SegmentTree
SegmentTree implements a segment tree over a fixed-size array of 32-bit integers, supporting range queries and point updates in O(log n).
Construction
| Syntax | Description |
|---|---|
SegmentTree(data) | Create a tree over the values in data |
The tree is built from a non-generic array of i32 values. Positions are zero-indexed from 0 to len - 1. The length may be zero.
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
update | (index: usize, value: i32) => void | void | Replace the element at index with value |
query | (from: usize, to: usize) => i32 | i32 | Return the sum of the range [from, to) |
len | () => usize | usize | Return the number of positions |
isEmpty | () => boolean | boolean | Whether the tree has no positions |
Ranges use an exclusive upper bound: query(from, to) sums the elements at positions from through to - 1, so query(0, len) is the total over all positions and query(k, k) is 0. update aborts with a runtime error when index >= len; query aborts when from > to or to > len.
Complexity
| Operation | Time Complexity |
|---|---|
update | O(log n) |
query | O(log n) |
len | O(1) |
isEmpty | O(1) |
Examples
Construction
tyrus
import { SegmentTree } from "tyrus:algorithm";
const st = SegmentTree([1, 3, 5, 7, 9, 11]);query
tyrus
const st = SegmentTree([1, 3, 5, 7, 9, 11]);
print(st.query(0, 6)); // 1 + 3 + 5 + 7 + 9 + 11
print(st.query(0, 3)); // 1 + 3 + 5
print(st.query(2, 5)); // 5 + 7 + 9
print(st.query(1, 2)); // 3update
tyrus
const st = SegmentTree([1, 3, 5, 7, 9, 11]);
st.update(0, 2);
st.update(5, 4);
print(st.query(0, 6)); // 2 + 3 + 5 + 7 + 9 + 4Negative values
tyrus
const st = SegmentTree([10, 20, 30]);
st.update(1, -5);
print(st.query(0, 2)); // 10 + (-5)
print(st.query(0, 3)); // 10 + (-5) + 30len and isEmpty
tyrus
const st = SegmentTree([]);
print(st.isEmpty()); // true
print(st.len()); // 0