Skip to content

SegmentTree ​

SegmentTree implementa un árbol de segmentos sobre un arreglo de tamaño fijo de enteros de 32 bits, con soporte de consultas por intervalo y actualizaciones puntuales en O(log n).

Construcción ​

SintaxisDescripción
SegmentTree(data)Crea un árbol sobre los valores en 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étodoFirmaRetornaDescripción
update(index: usize, value: i32) => voidvoidReemplaza el elemento en index por value
query(from: usize, to: usize) => i32i32Retorna la suma del intervalo [from, to)
len() => usizeusizeRetorna el número de posiciones
isEmpty() => booleanbooleanSi el árbol no tiene posiciones

Los intervalos usan límite superior exclusivo: query(from, to) suma los elementos en las posiciones from hasta to - 1, así que query(0, len) es el total sobre todas las posiciones y query(k, k) es 0. update aborta con error de runtime cuando index >= len; query aborta cuando from > to o to > len.

Complejidad ​

OperaciónComplejidad Temporal
updateO(log n)
queryO(log n)
lenO(1)
isEmptyO(1)

Ejemplos ​

Construcción ​

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

Valores negativos ​

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 e isEmpty ​

tyrus
const st = SegmentTree([]);

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