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
| Sintaxe | Descriçã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étodo | Assinatura | Retorna | Descrição |
|---|---|---|---|
add | (index: usize, delta: i32) => void | void | Adiciona delta ao elemento em index |
sum | (index: usize) => i32 | i32 | Retorna a soma dos primeiros index elementos, ou seja, o intervalo [0, index) |
len | () => usize | usize | Retorna o número de posições |
isEmpty | () => boolean | boolean | Se 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ção | Complexidade Temporal |
|---|---|
add | O(log n) |
sum | O(log n) |
len | O(1) |
isEmpty | O(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 + 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