SegmentTreeLazy
SegmentTreeLazy implementa un árbol de segmentos sobre un arreglo de tamaño fijo de enteros de 32 bits, con soporte para consultas por intervalo y sumas por intervalo en O(log n) mediante propagación perezosa.
Construcción
| Sintaxis | Descripción |
|---|---|
SegmentTreeLazy(data) | Crea un árbol sobre los valores de data |
El árbol se construye a partir de un arreglo no genérico de valores i32. Las posiciones se indexan desde cero, de 0 a len - 1. La longitud puede ser cero.
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
updateRange | (from: usize, to: usize, delta: i32) => void | void | Suma delta a cada elemento de [from, to) |
query | (from: usize, to: usize) => i32 | i32 | Devuelve la suma del intervalo [from, to) |
len | () => usize | usize | Devuelve el número de posiciones |
isEmpty | () => boolean | boolean | Indica si el árbol no tiene posiciones |
Los intervalos usan un límite superior exclusivo: query(from, to) suma los elementos de las posiciones desde from hasta to - 1, y updateRange(from, to, delta) suma delta a esas mismas posiciones. query(k, k) devuelve 0 y updateRange(k, k, delta) no tiene efecto. Ambos métodos de intervalo abortan con un error de runtime cuando from > to o to > len.
Complejidad
| Operación | Complejidad temporal |
|---|---|
updateRange | O(log n) |
query | O(log n) |
len | O(1) |
isEmpty | O(1) |
Ejemplos
Construcción y 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)); // 45Deltas negativos y árboles vacíos
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