Skip to content

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 ​

SintaxisDescripció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étodoFirmaDevuelveDescripción
updateRange(from: usize, to: usize, delta: i32) => voidvoidSuma delta a cada elemento de [from, to)
query(from: usize, to: usize) => i32i32Devuelve la suma del intervalo [from, to)
len() => usizeusizeDevuelve el número de posiciones
isEmpty() => booleanbooleanIndica 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ónComplejidad temporal
updateRangeO(log n)
queryO(log n)
lenO(1)
isEmptyO(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));  // 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

Deltas 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