Skip to content

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 ​

SyntaxDescription
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 ​

MethodSignatureReturnsDescription
update(index: usize, value: i32) => voidvoidReplace the element at index with value
query(from: usize, to: usize) => i32i32Return the sum of the range [from, to)
len() => usizeusizeReturn the number of positions
isEmpty() => booleanbooleanWhether 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 ​

OperationTime Complexity
updateO(log n)
queryO(log n)
lenO(1)
isEmptyO(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));  // 3

update ​

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 + 4

Negative 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) + 30

len and isEmpty ​

tyrus
const st = SegmentTree([]);

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