Skip to content

SegmentTreeLazy ​

SegmentTreeLazy implements a segment tree over a fixed-size array of 32-bit integers, supporting range queries and range additions in O(log n) through lazy propagation.

Construction ​

SyntaxDescription
SegmentTreeLazy(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
updateRange(from: usize, to: usize, delta: i32) => voidvoidAdd delta to every element in [from, to)
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, and updateRange(from, to, delta) adds delta to those same positions. query(k, k) returns 0 and updateRange(k, k, delta) has no effect. Both range methods abort with a runtime error when from > to or to > len.

Complexity ​

OperationTime Complexity
updateRangeO(log n)
queryO(log n)
lenO(1)
isEmptyO(1)

Examples ​

Construction and query ​

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

const st = SegmentTreeLazy([1, 3, 5, 7, 9, 11]);

print(st.query(0, 6));  // 36
print(st.query(2, 5));  // 21

updateRange ​

tyrus
const st = SegmentTreeLazy([1, 3, 5, 7, 9, 11]);

st.updateRange(1, 4, 10);

print(st.query(0, 6));  // 66
print(st.query(1, 4));  // 45

Negative deltas and empty trees ​

tyrus
const st = SegmentTreeLazy([10, 20, 30]);

st.updateRange(1, 3, -5);

print(st.query(0, 3));  // 50

const empty: i32[] = [];
const emptyTree = SegmentTreeLazy(empty);
print(emptyTree.isEmpty());  // true
print(emptyTree.len());      // 0