Skip to content

FenwickTree ​

FenwickTree implementa uma árvore de Fenwick (binary indexed tree) sobre um array de tamanho fixo de inteiros de 32 bits, com suporte a somas de prefixo e atualizações pontuais em O(log n).

Construção ​

SintaxeDescrição
FenwickTree(n)Cria uma árvore sobre n posições inicializadas em zero

As posições são indexadas a partir de zero, de 0 a n - 1. O comprimento n pode ser zero.

Métodos ​

MétodoAssinaturaRetornaDescrição
add(index: usize, delta: i32) => voidvoidAdiciona delta ao elemento em index
sum(index: usize) => i32i32Retorna a soma dos primeiros index elementos, ou seja, o intervalo [0, index)
len() => usizeusizeRetorna o número de posições
isEmpty() => booleanbooleanSe a árvore não tem posições

sum(index) retorna a soma dos primeiros index elementos (limite superior exclusivo): sum(0) é 0 e sum(n) é o total sobre todas as posições. add aborta com erro de runtime quando index >= n; sum aborta quando index > n.

Complexidade ​

OperaçãoComplexidade Temporal
addO(log n)
sumO(log n)
lenO(1)
isEmptyO(1)

Exemplos ​

Construção ​

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