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
| Syntax | Description |
|---|---|
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
| Method | Signature | Returns | Description |
|---|---|---|---|
updateRange | (from: usize, to: usize, delta: i32) => void | void | Add delta to every element in [from, to) |
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, 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
| Operation | Time Complexity |
|---|---|
updateRange | O(log n) |
query | O(log n) |
len | O(1) |
isEmpty | O(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)); // 21updateRange
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)); // 45Negative 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