Skip to content

SegmentTreeLazy ​

SegmentTreeLazy implementa uma árvore de segmentos sobre um array de tamanho fixo de inteiros de 32 bits, com suporte a consultas por intervalo e adições por intervalo em O(log n) por meio de propagação preguiçosa.

Construção ​

SintaxeDescrição
SegmentTreeLazy(data)Cria uma árvore sobre os valores em data

A árvore é construída a partir de um array não genérico de valores i32. As posições são indexadas a partir de zero, de 0 a len - 1. O comprimento pode ser zero.

Métodos ​

MétodoAssinaturaRetornaDescrição
updateRange(from: usize, to: usize, delta: i32) => voidvoidAdiciona delta a cada elemento em [from, to)
query(from: usize, to: usize) => i32i32Retorna a soma do intervalo [from, to)
len() => usizeusizeRetorna o número de posições
isEmpty() => booleanbooleanInforma se a árvore não possui posições

Os intervalos usam limite superior exclusivo: query(from, to) soma os elementos das posições de from até to - 1, e updateRange(from, to, delta) adiciona delta às mesmas posições. query(k, k) retorna 0 e updateRange(k, k, delta) não tem efeito. Os dois métodos de intervalo abortam com um erro de runtime quando from > to ou to > len.

Complexidade ​

OperaçãoComplexidade de tempo
updateRangeO(log n)
queryO(log n)
lenO(1)
isEmptyO(1)

Exemplos ​

Construção e 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 e árvores vazias ​

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