Sesión 52: Árbol Binario Indexado (Fenwick Tree / BIT) y Prefijos Dinámicos (LeetCode 307)#

Navegación rápida:

• ← Sesión 51: Monotonic Deque & Sliding Window Maximum (LeetCode 239)
• Sesión 53: Segment Tree: Consultas de Rango y Actualizaciones Perezosas (Lazy Propagation) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_52.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión estudiamos una de las estructuras de datos más compactas y elegantes inventadas en ciencias de la computación: el Árbol Binario Indexado (Binary Indexed Tree o Fenwick Tree, propuesto por Peter Fenwick en 1994). Consulta el Glosario Maestro y la Guía de Diagramas.

Fenwick Tree / Binary Indexed Tree (BIT)#

• (a) En palabras simples (intuición): Imagina que quieres calcular la suma de ventas de una tienda entre el día 10 y el día 50. Si sumas día por día, tardas mucho (O(N)). Si mantienes una tabla con las sumas acumuladas ya calculadas desde el día 1, responder la consulta toma un parpadeo (O(1)), pero si el cajero corrige una venta del día 5, tendrías que recalcular todas las sumas de los días siguientes (O(N)). El Fenwick Tree es el compromiso perfecto: organiza las sumas en paquetes de potencias de 2 (1, 2, 4, 8…), permitiendo tanto actualizar un dato como sumar cualquier rango en apenas un puñado de pasos (≤ log₂ N).
• (b) Definición técnica paso a paso: Estructura de datos implícita basada en un arreglo de tamaño N + 1 que mantiene sumas acumuladas de prefijos dinámicos. Utiliza indexación en base 1:
• Cada celda tree[i] es responsable de la suma del intervalo semiabierto (i - LSB(i), ; i].
• Consulta de Prefijo (query_prefix(i)): Suma tree[i] y asciende restando el LSB: i = i - LSB(i) hasta llegar a 0. Complejidad: O(log N).
• Actualización Puntual (add(i, delta)): Suma delta a tree[i] y propaga el cambio sumando el LSB: i = i + LSB(i) hasta superar N. Complejidad: O(log N).
• Espacio: O(N) estricto en un único vector contiguo, sin punteros de árbol explícitos.
• (c) Cómo funciona en Rust (memoria y tipos): El cálculo del bit menos significativo en tipos sin signo usize se realiza mediante la operación idiomática i & i.wrapping_neg(). Al no haber punteros Box ni indirecciones, toda la estructura es un simple Vec<i64>.
• (d) Error típico de Junior: Intentar usar indexación en base 0; si i = 0, LSB(0) = 0, lo que provoca bucles infinitos inmediatos (0 + 0 = 0).

LSB (Least Significant Bit / Bit Menos Significativo en 1)#

• (a) En palabras simples (intuición): Es una linterna que apunta exclusivamente al interruptor encendido (1) que esté más a la derecha en la representación binaria de un número, apagando todos los demás interruptores. Por ejemplo, en 12 = 1100₂, el último 1 está en la posición del 4 (0100₂). Por tanto, LSB(12) = 4.
• (b) Definición técnica paso a paso: Operación algebraica bitwise que aísla la potencia de 2 más baja presente en i:

En complemento a dos, -i = (!i) + 1. Al hacer la conjunción AND, todos los bits superiores se anulan y solo sobrevive el bit 1 menos significativo.

• (c) Cómo funciona en Rust (memoria y tipos): En Rust, usize es un tipo sin signo y no permite el operador unario -i. Se calcula de forma idiomática y sin pánico con i & i.wrapping_neg(). En x86_64 compila a la instrucción nativa BLSI (o neg + and).
• (d) Error típico de Junior: Escribir i as isize y - (i as isize) con castings ruidosos en cada iteración del bucle.

Binary Lifting sobre Fenwick Tree (O(log N))#

• (a) En palabras simples (intuición): Quieres encontrar en qué día las ventas acumuladas superaron los \10,000. En lugar de hacer una búsqueda binaria tradicional que llamaría a CODE0 repetidas veces (O(\log^2 N)), caminas sobre el árbol dando pasos gigantescos de potencias de 2 (16, 8, 4, 2, 1$ casillas). En cada paso miras si cabe el paquete de suma sin pasarte del objetivo, logrando la respuesta en un solo salto logarítmico (O(log N)).
• (b) Definición técnica paso a paso: Técnica de búsqueda binaria interna sobre las potencias de 2 decrecientes acumuladas en el BIT. Comienza con la mayor potencia de 2 menor o igual a N. Si acumular el nodo idx + power no supera el umbral target_sum, se avanza el índice y se suma el valor; luego se divide la potencia entre dos. Resuelve lower_bound sobre sumas de prefijos monótonas en O(log N) estricto.
• (c) Cómo funciona en Rust (memoria y tipos): Un simple bucle while power > 0 { ... power >>= 1; } ejecutado enteramente en registros de CPU.
• (d) Error típico de Junior: Aplicar Binary Lifting en arreglos con números negativos; el lifting binario exige monotonía estricta en las sumas de prefijo (elementos no negativos).

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Cobertura de Intervalos en Fenwick Tree#

¿Qué intervalo de números exactos almacena la casilla tree[i]?

La regla fundamental de Fenwick establece:

Analicemos las primeras 8 posiciones:

• 1 = 0001₂ ⟹ LSB(1) = 1. Intervalo: (1 - 1 + 1 .. 1] = [1..1]. Almacena: nums[1].
• 2 = 0010₂ ⟹ LSB(2) = 2. Intervalo: (2 - 2 + 1 .. 2] = [1..2]. Almacena: nums[1] + nums[2].
• 3 = 0011₂ ⟹ LSB(3) = 1. Intervalo: (3 - 1 + 1 .. 3] = [3..3]. Almacena: nums[3].
• 4 = 0100₂ ⟹ LSB(4) = 4. Intervalo: (4 - 4 + 1 .. 4] = [1..4]. Almacena: nums[1] + … + nums[4].
• 5 = 0101₂ ⟹ LSB(5) = 1. Intervalo: [5..5]. Almacena: nums[5].
• 6 = 0110₂ ⟹ LSB(6) = 2. Intervalo: [5..6]. Almacena: nums[5] + nums[6].
• 7 = 0111₂ ⟹ LSB(7) = 1. Intervalo: [7..7]. Almacena: nums[7].
• 8 = 1000₂ ⟹ LSB(8) = 8. Intervalo: [1..8]. Almacena: nums[1] + … + nums[8].

Observa la estructura jerárquica:

• Las posiciones impares (1, 3, 5, 7) tienen LSB = 1 y son hojas que solo guardan su propio valor.
• Las potencias exactas de dos (2, 4, 8) almacenan el prefijo completo acumulado desde el inicio hasta esa posición.

Construcción Lineal en O(N) vs O(N log N)#

Un enfoque ingenuo para construir el Fenwick Tree ejecuta N llamadas a add(i, nums[i]), lo que toma N × O(log N) = O(N log N) tiempo.

Podemos construir el árbol en estricto tiempo lineal O(N) mediante una sola pasada hacia adelante:

1. Copiamos nums[i - 1] en tree[i].
2. El nodo padre directo e inmediato que contiene a i en su rango es:
   parent = i + LSB(i)
3. Si parent ≤ N, sumamos directamente el contenido acumulado de tree[i] a tree[parent].
4. Al iterar en orden ascendente de $1$ a N, cuando llegamos a cualquier nodo su valor ya incluye la suma de todos sus subárboles inferiores.
5. Complejidad: Exactamente N sumas ⟹ O(N).

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Responsabilidad de Nodos en Fenwick Tree#

Consulta el diagrama vectorial:

flowchart TD
    N8["tree[8]: [1..8]"]
    N4["tree[4]: [1..4]"] --> N8
    N6["tree[6]: [5..6]"] --> N8
    N7["tree[7]: [7..7]"] --> N8
    N2["tree[2]: [1..2]"] --> N4
    N3["tree[3]: [3..3]"] --> N4
    N1["tree[1]: [1..1]"] --> N2
    N5["tree[5]: [5..5]"] --> N6

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Construcción lineal sobre arr = [1, 2, 3, 4, 5, 6, 7, 8]:

STACK:
[ ft: FenwickTree { n: 8, tree: Vec<i64>, original: Vec<i32> } ]

HEAP (Vector tree de tamaño n + 1 = 9):
Índice:     [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]   [8]
Inicial:     0     1     2     3     4     5     6     7     8

PASO A PASO DEL BUCLE LINEAL:
i = 1: LSB(1) = 1 -> parent = 2. tree[2] += tree[1] (2 + 1 = 3)
i = 2: LSB(2) = 2 -> parent = 4. tree[4] += tree[2] (4 + 3 = 7)
i = 3: LSB(3) = 1 -> parent = 4. tree[4] += tree[3] (7 + 3 = 10)
i = 4: LSB(4) = 4 -> parent = 8. tree[8] += tree[4] (8 + 10 = 18)
i = 5: LSB(5) = 1 -> parent = 6. tree[6] += tree[5] (6 + 5 = 11)
i = 6: LSB(6) = 2 -> parent = 8. tree[8] += tree[6] (18 + 11 = 29)
i = 7: LSB(7) = 1 -> parent = 8. tree[8] += tree[7] (29 + 7 = 36)
i = 8: LSB(8) = 8 -> parent = 16 > 8 (ignorado)

ESTADO FINAL EN HEAP (tree):
[0]=0, [1]=1, [2]=3, [3]=3, [4]=10, [5]=5, [6]=11, [7]=7, [8]=36
Verificación: tree[8] = 1+2+3+4+5+6+7+8 = 36. ¡Exacto en O(N)!

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: El Bucle Infinito del Cero en Fenwick Tree#

• El error: Llamar a add(0, val) o permitir que index_1based llegue a 0 en una actualización.
• Por qué falla: LSB(0) = 0 & (-0) = 0. La instrucción i += LSB(i) se convierte en 0 += 0, atrapando al procesador en un bucle infinito que nunca avanza.
• La solución: Fenwick Tree debe ser obligatoriamente 1-based internamente. Al recibir un índice de entrada 0-based de LeetCode, sumar siempre +1 antes de tocar el árbol:

  self.add(index_0based + 1, delta);

Trampa 2: Sobrescritura en Lugar de Diferencia (Delta) en update()#

• El error: Escribir tree[i] = val al actualizar un elemento.
• Por qué falla: Cada nodo del Fenwick Tree almacena una suma agregada de múltiples elementos. Sobrescribir el valor destruye las sumas históricas de los otros elementos que comparten esa cubeta.
• La solución: Calcular la diferencia Δ = nuevo_valor - valor_antiguo, actualizar el arreglo original y propagar delta sumando:

  let delta = val as i64 - self.original[index_0based] as i64;
  self.original[index_0based] = val;
  self.add(index_0based + 1, delta);

Trampa 3: Desbordamiento Numérico al Sumar Rangos Grandes#

• El error: Usar i32 para el arreglo tree en problemas con arreglos de N = 10⁵ elementos con valores de hasta 10⁹.
• Por qué falla: La suma acumulada puede alcanzar 10⁵ × 10⁹ = 10¹⁴, superando holgadamente el límite de 2 × 10⁹ de un entero de 32 bits y causando pánicos por overflow o sumas corruptas negativas.
• La solución: Utilizar siempre enteros de 64 bits i64 para el buffer del árbol acumulador tree: Vec<i64>.

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_52.rs)#

/// Fenwick Tree (Binary Indexed Tree) Canónico 1-based en Rust.
#[derive(Debug, Clone)]
pub struct FenwickTree {
    n: usize,
    tree: Vec<i64>,
    original: Vec<i32>,
}

impl FenwickTree {
    /// Construcción lineal en O(N).
    pub fn from_slice(arr: &[i32]) -> Self {
        let n = arr.len();
        let mut ft = Self {
            n,
            tree: vec![0; n + 1],
            original: arr.to_vec(),
        };

        for i in 1..=n {
            ft.tree[i] += ft.original[i - 1] as i64;
            let parent = i + (i & i.wrapping_neg());
            if parent <= n {
                ft.tree[parent] += ft.tree[i];
            }
        }
        ft
    }

    /// Añade delta a index_1based en O(log N).
    pub fn add(&mut self, mut index_1based: usize, delta: i64) {
        if index_1based == 0 || index_1based > self.n {
            return;
        }
        while index_1based <= self.n {
            self.tree[index_1based] += delta;
            index_1based += index_1based & index_1based.wrapping_neg();
        }
    }

    /// Actualiza el valor en index_0based en O(log N).
    pub fn update(&mut self, index_0based: usize, val: i32) {
        if index_0based >= self.n {
            return;
        }
        let delta = val as i64 - self.original[index_0based] as i64;
        self.original[index_0based] = val;
        self.add(index_0based + 1, delta);
    }

    /// Consulta de prefijo [1..=index_1based] en O(log N).
    pub fn query_prefix(&self, mut index_1based: usize) -> i64 {
        if index_1based == 0 {
            return 0;
        }
        if index_1based > self.n {
            index_1based = self.n;
        }
        let mut total = 0i64;
        while index_1based > 0 {
            total += self.tree[index_1based];
            index_1based -= index_1based & index_1based.wrapping_neg();
        }
        total
    }

    /// Consulta de rango [left_0based..=right_0based] en O(log N).
    pub fn query_range(&self, left_0based: usize, right_0based: usize) -> i64 {
        if left_0based > right_0based || right_0based >= self.n {
            return 0;
        }
        self.query_prefix(right_0based + 1) - self.query_prefix(left_0based)
    }
}

Implementación de Referencia en Python (practica/dia_52_fenwick_tree_binary_indexed_tree.py)#

from typing import List


class FenwickTree:
    """BIT 1-based canónico en Python."""

    def __init__(self, arr: List[int]) -> None:
        self.n = len(arr)
        self.original = list(arr)
        self.tree = [0] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.tree[i] += self.original[i - 1]
            parent = i + (i & (-i))
            if parent <= self.n:
                self.tree[parent] += self.tree[i]

    def add(self, index_1based: int, delta: int) -> None:
        i = index_1based
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def update(self, index_0based: int, val: int) -> None:
        delta = val - self.original[index_0based]
        self.original[index_0based] = val
        self.add(index_0based + 1, delta)

    def query_prefix(self, index_1based: int) -> int:
        total = 0
        i = index_1based
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def query_range(self, left_0based: int, right_0based: int) -> int:
        if left_0based > right_0based:
            return 0
        return self.query_prefix(right_0based + 1) - self.query_prefix(left_0based)

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Rango de un Solo Elemento (L = R): - Para cualquier arreglo arr, verifica que ft.query_range(3, 3) retorne exactamente el valor original de arr[3].
2. Paso Límite 2: Arreglo de Tamaño Potencia de Dos (N = 8): - Verifica que ft.query_prefix(8) se resuelva en un único salto de memoria de tiempo O(1), ya que 8 - LSB(8) = 8 - 8 = 0.
3. Paso Límite 3: Fenwick Tree 2D (Matrices): - Diseña un Fenwick Tree bidimensional de tamaño M × N para calcular sumas de submatrices dinámicas en tiempo O(log M · log N) anidando dos bucles de LSB.

Navegación final:

• ← Sesión 51: Monotonic Deque & Sliding Window Maximum (LeetCode 239)
• Sesión 53: Segment Tree: Consultas de Rango y Actualizaciones Perezosas (Lazy Propagation) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura