FenwickTree
FenwickTree implementa un árbol de Fenwick (binary indexed tree) sobre un arreglo de tamaño fijo de enteros de 32 bits, con soporte de sumas de prefijo y actualizaciones puntuales en O(log n).
Construcción
| Sintaxis | Descripción |
|---|---|
FenwickTree(n) | Crea un árbol sobre n posiciones inicializadas en cero |
Las posiciones se indexan desde cero, de 0 a n - 1. La longitud n puede ser cero.
Métodos
| Método | Firma | Retorna | Descripción |
|---|---|---|---|
add | (index: usize, delta: i32) => void | void | Agrega delta al elemento en index |
sum | (index: usize) => i32 | i32 | Retorna la suma de los primeros index elementos, es decir, el intervalo [0, index) |
len | () => usize | usize | Retorna el número de posiciones |
isEmpty | () => boolean | boolean | Si el árbol no tiene posiciones |
sum(index) retorna la suma de los primeros index elementos (límite superior exclusivo): sum(0) es 0 y sum(n) es el total sobre todas las posiciones. add aborta con error de runtime cuando index >= n; sum aborta cuando index > n.
Complejidad
| Operación | Complejidad Temporal |
|---|---|
add | O(log n) |
sum | O(log n) |
len | O(1) |
isEmpty | O(1) |
Ejemplos
Construcción
tyrus
import { FenwickTree } from "tyrus:algorithm";
const bit = FenwickTree(6);add
tyrus
const bit = FenwickTree(4);
bit.add(0, 1);
bit.add(1, 2);
bit.add(2, 3);
bit.add(3, 4);sum
tyrus
const bit = FenwickTree(4);
bit.add(0, 1);
bit.add(1, 2);
bit.add(2, 3);
bit.add(3, 4);
print(bit.sum(0)); // 0
print(bit.sum(1)); // 1
print(bit.sum(3)); // 1 + 2 + 3
print(bit.sum(4)); // 1 + 2 + 3 + 4Deltas negativos
tyrus
const bit = FenwickTree(3);
bit.add(0, 10);
bit.add(1, 20);
bit.add(2, 30);
bit.add(1, -5);
print(bit.sum(2)); // 10 + 15
print(bit.sum(3)); // 10 + 15 + 30len e isEmpty
tyrus
const bit = FenwickTree(0);
print(bit.isEmpty()); // true
print(bit.len()); // 0