SegmentTree
SegmentTree implementa uma árvore de segmentos sobre um array de tamanho fixo de inteiros de 32 bits, com suporte a consultas por intervalo e atualizações pontuais em O(log n).
Construção
| Sintaxe | Descrição |
|---|---|
SegmentTree(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étodo | Assinatura | Retorna | Descrição |
|---|---|---|---|
update | (index: usize, value: i32) => void | void | Substitui o elemento em index por value |
query | (from: usize, to: usize) => i32 | i32 | Retorna a soma do intervalo [from, to) |
len | () => usize | usize | Retorna o número de posições |
isEmpty | () => boolean | boolean | Se a árvore não tem posições |
Os intervalos usam limite superior exclusivo: query(from, to) soma os elementos nas posições from até to - 1, então query(0, len) é o total sobre todas as posições e query(k, k) é 0. update aborta com erro de runtime quando index >= len; query aborta quando from > to ou to > len.
Complexidade
| Operação | Complexidade Temporal |
|---|---|
update | O(log n) |
query | O(log n) |
len | O(1) |
isEmpty | O(1) |
Exemplos
Construção
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