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
| Sintaxis | Descripció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étodo | Firma | Retorna | Descripción |
|---|---|---|---|
update | (index: usize, value: i32) => void | void | Reemplaza el elemento en index por value |
query | (from: usize, to: usize) => i32 | i32 | Retorna la suma del intervalo [from, to) |
len | () => usize | usize | Retorna el número de posiciones |
isEmpty | () => boolean | boolean | Si 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ón | Complejidad Temporal |
|---|---|
update | O(log n) |
query | O(log n) |
len | O(1) |
isEmpty | O(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)); // 3update
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 + 4Valores 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) + 30len e isEmpty
tyrus
const st = SegmentTree([]);
print(st.isEmpty()); // true
print(st.len()); // 0