Skip to content

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 ​

SintaxisDescripció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étodoFirmaRetornaDescripción
add(index: usize, delta: i32) => voidvoidAgrega delta al elemento en index
sum(index: usize) => i32i32Retorna la suma de los primeros index elementos, es decir, el intervalo [0, index)
len() => usizeusizeRetorna el número de posiciones
isEmpty() => booleanbooleanSi 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ónComplejidad Temporal
addO(log n)
sumO(log n)
lenO(1)
isEmptyO(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 + 4

Deltas 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 + 30

len e isEmpty ​

tyrus
const bit = FenwickTree(0);

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