Data Structure & Algorithms
Estructuras especializadas para prefijos y rangos: tries, Fenwick trees y segment trees, con consultas, actualizaciones y trade-offs.
Tries, Fenwick trees y segment trees resuelven consultas que estructuras más generales manejan con demasiado trabajo repetido.
Son estructuras avanzadas porque su utilidad depende de reconocer una operación muy específica, no porque deban usarse en todo sistema.
Un trie representa una palabra como un camino de caracteres.
(root)
├─ c ─ a ─ t*
│ └─ r*
└─ d ─ o ─ g*El asterisco indica que el camino forma una palabra completa. Un nodo puede ser prefijo válido sin ser una palabra.
Para una clave de longitud L:
O(L);O(L);O(L).La complejidad no depende directamente de la cantidad de palabras, pero la memoria puede ser alta por la cantidad de nodos y referencias.
class TrieNode {
readonly children = new Map<string, TrieNode>();
isWord = false;
}
class Trie {
private readonly root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const character of word) {
let child = node.children.get(character);
if (!child) {
child = new TrieNode();
node.children.set(character, child);
}
node = child;
}
node.isWord = true;
}
has(word: string): boolean {
const node = this.findNode(word);
return node?.isWord ?? false;
}
hasPrefix(prefix: string): boolean {
return this.findNode(prefix) !== undefined;
}
private findNode(text: string): TrieNode | undefined {
let node = this.root;
for (const character of text) {
const child = node.children.get(character);
if (!child) return undefined;
node = child;
}
return node;
}
}for...of recorre code points, no necesariamente grapheme clusters visibles. Además, textos visualmente iguales pueden tener representaciones Unicode distintas. Una aplicación real debe decidir normalización, mayúsculas, acentos e idioma antes de insertar claves.
No conviene cuando solo necesitas lookup exacto: un Map suele ser más simple y compacto.
Un Fenwick tree o Binary Indexed Tree mantiene prefix sums con actualizaciones puntuales.
Problema base:
values[index];0..index;Ambas operaciones cuestan O(log n).
Cada posición almacena un bloque cuyo tamaño está determinado por el bit menos significativo:
index binary block size
1 0001 1
2 0010 2
4 0100 4
6 0110 2Se suele usar indexación desde 1 para que index & -index identifique ese bloque.
class FenwickTree {
private readonly tree: number[];
constructor(size: number) {
this.tree = Array(size + 1).fill(0);
}
add(index: number, delta: number): void {
for (let current = index + 1; current < this.tree.length; ) {
this.tree[current] += delta;
current += current & -current;
}
}
prefixSum(index: number): number {
let sum = 0;
for (let current = index + 1; current > 0; ) {
sum += this.tree[current];
current -= current & -current;
}
return sum;
}
rangeSum(left: number, right: number): number {
if (left > right) return 0;
return this.prefixSum(right) - this.prefixSum(left - 1);
}
}Tiempo por actualización y consulta: O(log n). Memoria: O(n).
La implementación recibe índices externos desde 0 y los convierte internamente a 1.
Funciona especialmente bien cuando la operación puede invertirse para obtener un rango desde dos prefijos, como suma:
sum(left..right) = prefix(right) - prefix(left - 1)No todas las operaciones permiten esa resta. Para mínimos con actualizaciones arbitrarias, un segment tree suele ser más apropiado.
Un segment tree divide el array en rangos jerárquicos.
[0..7]
/ \
[0..3] [4..7]
/ \ / \
[0..1] [2..3] [4..5] [6..7]Cada nodo guarda un agregado de su rango: suma, mínimo, máximo, gcd u otra operación asociativa.
Para consultar [left, right]:
En un árbol balanceado, una consulta y una actualización puntual cuestan O(log n).
class SegmentTree {
private readonly size: number;
private readonly tree: number[];
constructor(values: number[]) {
let size = 1;
while (size < values.length) size *= 2;
this.size = size;
this.tree = Array(size * 2).fill(0);
for (let i = 0; i < values.length; i += 1) {
this.tree[size + i] = values[i];
}
for (let node = size - 1; node > 0; node -= 1) {
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
}
update(index: number, value: number): void {
let node = this.size + index;
this.tree[node] = value;
while (node > 1) {
node = Math.floor(node / 2);
this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
}
}
query(left: number, right: number): number {
let from = left + this.size;
let to = right + this.size;
let result = 0;
while (from <= to) {
if (from % 2 === 1) result += this.tree[from++];
if (to % 2 === 0) result += this.tree[to--];
from = Math.floor(from / 2);
to = Math.floor(to / 2);
}
return result;
}
}Esta versión usa suma y consultas inclusivas. El elemento neutro es 0. Para mínimo sería Infinity; para máximo, -Infinity.
Si necesitas actualizar rangos completos, modificar cada elemento cuesta O(n). Lazy propagation guarda actualizaciones pendientes en nodos y las propaga solo cuando una consulta desciende.
Permite actualizaciones y consultas de rango en O(log n) en muchas variantes, a cambio de una implementación bastante más delicada.
| Estructura | Problema principal | Consulta | Actualización | Memoria |
|---|---|---|---|---|
| Prefix sum | Rangos sin cambios | O(1) | O(n) | O(n) |
| Fenwick | Sumas y updates puntuales | O(log n) | O(log n) | O(n) |
| Segment tree | Agregados generales de rango | O(log n) | O(log n) | O(n) |
| Trie | Claves y prefijos | O(L) | O(L) | Depende de nodos |
0 y base 1 en Fenwick.index & -index sin comprender cuándo el índice puede ser cero.Tienes un array que nunca cambia y miles de consultas de suma por rango. ¿Necesitas Fenwick o segment tree?
No. Un prefix sum se construye en O(n) y responde cada rango en O(1). Las estructuras dinámicas solo aportan valor cuando también existen actualizaciones.