Sesión 53: Árbol de Segmentos (Segment Tree): Consultas de Rango y Actualizaciones en O(log N)#

Navegación rápida:

• ← Sesión 52: Árbol Binario Indexado (Fenwick Tree / BIT) y Prefijos Dinámicos
• Sesión 54: Algoritmo de Kadane: Máxima Submatriz y Variantes Circulares (CTCI 17.24) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_53.rs

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

En esta sesión abordamos el Árbol de Segmentos (Segment Tree), la estructura de datos por excelencia para resolver problemas de consultas sobre rangos dinámicos arbitrarios bajo cualquier operación asociativa. Consulta el Glosario Maestro y la Guía de Diagramas.

Segment Tree (Árbol de Segmentos)#

• (a) En palabras simples (intuición): Imagina un organigrama de una empresa donde la oficina central supervisa toda la cadena de tiendas (del local 0 al local N-1). Debajo hay dos gerentes regionales: uno supervisa la mitad izquierda y otro la mitad derecha. En la base del árbol, cada empleado cuida una sola tienda. Si preguntas: "¿cuál fue la tienda con más ventas entre el local 3 y el 8?", no visitas las 6 tiendas una por una: le preguntas a los gerentes que cubren exactamente esos tramos y combinas sus respuestas en un par de pasos.
• (b) Definición técnica paso a paso: Árbol binario estático y balanceado donde cada nodo representa un intervalo cerrado [L, R] de un arreglo:
• La raíz (nodo 1) representa el rango global [0, N - 1].
• Un nodo que cubre [L, R] se bifurca en su punto medio mid = ⌊ (L + R) / 2 ⌋:
• Hijo izquierdo (2 * node): Cubre [L, mid].
• Hijo derecho (2 * node + 1): Cubre [mid + 1, R].
• Las hojas cubren intervalos unitarios [i, i].
• Admite cualquier monoide asociativo: suma, mínimo, máximo, gcd, multiplicación de matrices.
• (c) Cómo funciona en Rust (memoria y tipos): Se almacena en un buffer lineal plano Vec<T> de tamaño 4N. La indexación utiliza aritmética de enteros: lc = 2 * node, rc = 2 * node + 1.
• (d) Error típico de Junior: Reservar un arreglo de tamaño 2N; si N no es potencia exacta de 2, el árbol binario no es perfecto y los índices de las hojas pueden llegar hasta casi 4N, provocando accesos fuera de rango (panic out of bounds).

Mapeo en Memoria Contigua 4 * N (Array-based Tree)#

• (a) En palabras simples (intuición): En lugar de crear cajitas sueltas conectadas con flechas y punteros por toda la memoria, pegas todas las ramas en un solo listón de madera largo y numerado. Para visitar a tu hijo izquierdo multiplicas tu número por 2; para el derecho multiplicas por 2 y sumas 1.
• (b) Definición técnica paso a paso: Representación implícita de árboles binarios en un único vector continuo, idéntica a la utilizada en los montículos binarios (Binary Heaps):
• Raíz en el índice 1.
• Para un nodo en la posición p:
  Hijo Izquierdo = 2p
  Hijo Derecho = 2p + 1
  Padre = ⌊ p / 2 ⌋
• (c) Cómo funciona en Rust (memoria y tipos): Se preasigna vec![0; 4 * n] en el Heap. Aprovecha de forma inigualable la caché L1 del procesador al evitar la fragmentación de memoria.
• (d) Error típico de Junior: Empezar la raíz en el índice 0; si la raíz está en 0, 2 × 0 = 0 y el hijo colisionaría con el propio padre.

Las 3 Condiciones de Solapamiento en Consultas de Rango#

• (a) En palabras simples (intuición): Cuando buscas información sobre un rango [QL, QR] y miras un nodo que cubre [start, end]:

1. Totalmente adentro: El nodo completo cabe dentro de lo que buscas. Tomas su valor y te vas.
2. Totalmente afuera: El nodo no tiene nada que ver con lo que buscas. Lo ignoras (devuelves el valor neutro, como 0 para sumas o ∞ para mínimos).
3. A medias: El nodo tiene una parte adentro y otra afuera. Tienes que bajar a sus dos hijos para separar la paja del trigo.

• (b) Definición técnica paso a paso: Clasificación geométrica fundamental de la recursión en query_node:
• Inclusión Total (QL ≤ start land end ≤ QR): El intervalo del nodo es un subconjunto del rango de consulta ⟹ Retorna tree[node] en O(1).
• Disyunción Total (end < QL lor start > QR): La intersección es vacía ⟹ Retorna el elemento neutro (identidad).
• Intersección Parcial: Se calcula mid y se desciende recursivamente por ambos hijos, combinando sus resultados con la operación asociativa: combine(left_res, right_res).
• (c) Cómo funciona en Rust (memoria y tipos): La función recursiva recorre a lo sumo 4 log₂ N nodos, garantizando tiempo O(log N) estricto.
• (d) Error típico de Junior: Olvidar el caso de disyunción total y permitir que la recursión continúe bajando hasta las hojas inútilmente.

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

Demostración Matemática: ¿Por qué el Buffer Requiere 4N y no 2N?#

¿Por qué un Segment Tree sobre un arreglo de tamaño N puede requerir un arreglo de hasta 4N posiciones?

1. Sea N el tamaño del arreglo.
2. Si N es una potencia exacta de 2 (por ejemplo, N = 8 = 2³): - El árbol es un árbol binario perfecto de altura h = 3. - La cantidad total de nodos es:
   sum_{k=0}^{h} 2ᵏ = 2^{h+1} - 1 = 2N - 1 = 15 nodos
   - En este caso ideal, un buffer de 2N bastaría.
3. ¿Qué ocurre si N NO es potencia de 2? (por ejemplo, N = 5): - La menor potencia de 2 mayor o igual a 5 es 2^{⌈ log₂ 5 ⌉} = 2³ = 8. - El árbol tendrá la misma profundidad que un árbol de 8 hojas. - En la representación implícita en arreglo con saltos 2p y 2p + 1, el índice máximo asignado a una hoja puede llegar a:
   2 · 2^{⌈ log₂ N ⌉} - 1 < 2 · (2N) = 4N
4. Demostración Numérica: Para N = 5, la hoja en el extremo derecho se ubica en el índice $13$. $$13 > 2N = 10 \text{ (¡Un arreglo de 2N colapsaría con desbordamiento!)}$$ Como 13 ≤ 4N = 20, la cota superior universal matemáticamente segura es estrictamente 4N.

Demostración de Complejidad: ¿Por qué la Consulta es O(log N) si se Visitan Dos Hijos?#

En una consulta con solapamiento parcial, el algoritmo desciende recursivamente a ambos hijos:

let left_sum = self.query_node(left_child, start, mid, ql, qr);
let right_sum = self.query_node(right_child, mid + 1, end, ql, qr);

Un Trainee podría sospechar: "Si llamamos a los dos hijos, ¿la complejidad no se vuelve exponencial O(2^h) = O(N)?"

Prueba Formal de Acotamiento:

• En cualquier nivel de profundidad del árbol de segmentos, a lo sumo dos nodos pueden tener intersección parcial con el rango de consulta [QL, QR] (los que contienen las fronteras QL y QR).
• Todos los nodos completamente interiores caen en la condición de Inclusión Total y se detienen inmediatamente en O(1).
• Todos los nodos completamente exteriores caen en Disyunción Total y retornan inmediatamente en O(1).
• Como en cada uno de los log₂ N niveles solo se pueden ramificar a lo sumo 4 nodos:

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

Diagrama de Árbol de Segmentos sobre Arreglo de 4 Elementos#

Consulta el diagrama vectorial:

flowchart TD
    N1["Nodo 1: [0..3]<br/>Suma = 16"] --> N2["Nodo 2: [0..1]<br/>Suma = 4"]
    N1 --> N3["Nodo 3: [2..3]<br/>Suma = 12"]
    N2 --> N4["Nodo 4: [0..0]<br/>arr[0] = 1"]
    N2 --> N5["Nodo 5: [1..1]<br/>arr[1] = 3"]
    N3 --> N6["Nodo 6: [2..2]<br/>arr[2] = 5"]
    N3 --> N7["Nodo 7: [3..3]<br/>arr[3] = 7"]

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

Distribución en memoria del vector tree: Vec<i64> para arr = [1, 3, 5, 7] (N = 4, 4N = 16):

STACK:
[ st: SegmentTree { n: 4, tree: Vec<i64>, arr: Vec<i64> } ]

HEAP (Buffer de tree de 16 elementos):
Índice: [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8..15]
Valor:   0   16    4   12    1    3    5    7     0...
Rango:   -  [0..3][0..1][2..3][0..0][1..1][2..2][3..3]

CONSULTA: query_sum(ql = 1, qr = 2) (debe sumar arr[1] + arr[2] = 3 + 5 = 8):
Paso 1: Nodo 1 [0..3]: Solapamiento parcial. Lanza hijo 2 e hijo 3.
Paso 2:
  - En Hijo 2 [0..1]: Solapamiento parcial con [1..2]. Lanza hijo 4 e hijo 5.
    - Hijo 4 [0..0]: Fuera de rango ([1..2]) -> Retorna 0.
    - Hijo 5 [1..1]: Totalmente adentro ([1..2]) -> Retorna tree[5] = 3.
    - Hijo 2 retorna: 0 + 3 = 3.
  - En Hijo 3 [2..3]: Solapamiento parcial con [1..2]. Lanza hijo 6 e hijo 7.
    - Hijo 6 [2..2]: Totalmente adentro ([1..2]) -> Retorna tree[6] = 5.
    - Hijo 7 [3..3]: Fuera de rango ([1..2]) -> Retorna 0.
    - Hijo 3 retorna: 5 + 0 = 5.
Paso 3: Nodo 1 combina: left_sum (3) + right_sum (5) = 8.
Resultado retornado: 8.

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

Trampa 1: Error Off-by-One en el Cálculo del Punto Medio#

• El error: Escribir let mid = (start + end) / 2 con posibles desbordamientos, o confundir las fronteras dividiendo en [start, mid - 1] y [mid, end].
• Por qué falla: Si divides asimétricamente los intervalos, las hojas unitarias [i, i] pueden entrar en recursión infinita cuando start = 0, end = 1.
• La solución: Usar la partición estándar matemáticamente simétrica:

  let mid = start + (end - start) / 2;
  // Hijo izquierdo cubre [start..=mid]
  // Hijo derecho cubre [mid + 1..=end]

Trampa 2: Valor Neutro Incorrecto en Segment Tree de Mínimos/Máximos#

• El error: Retornar 0 en el caso de Disyunción Total al implementar un Segment Tree de Mínimos (Range Minimum Query).
• Por qué falla: Si todos los elementos del arreglo son números positivos grandes (ej. [100, 200, 300]), retornar 0 en un segmento fuera de rango contaminará la función min(), haciendo que el mínimo reportado sea erróneamente 0.
• La solución: Para consultas de mínimo, el valor neutro debe ser infinito positivo (i64::MAX); para consultas de máximo, infinito negativo (i64::MIN); y para sumas, el neutro aditivo 0.

Trampa 3: Reasignar la Capacidad del Árbol Dinámicamente en Recursión#

• El error: Usar llamadas a push dentro de la función de construcción del árbol en lugar de preasignar el vector completo.
• Por qué falla: El recorrido por índices 2 * node y 2 * node + 1 salta a casillas no secuenciales antes de que los índices intermedios hayan sido llenados, causando pánicos inmediatos de índice fuera de rango.
• La solución: Inicializar el vector con su tamaño completo preasignado en ceros:

  tree: vec![0; 4 * n]

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

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

/// Árbol de Segmentos Canónico para Range Sum Queries con buffer 4N.
#[derive(Debug, Clone)]
pub struct SegmentTree {
    n: usize,
    tree: Vec<i64>,
    arr: Vec<i64>,
}

impl SegmentTree {
    pub fn from_slice(slice: &[i64]) -> Self {
        let n = slice.len();
        let tree_size = if n > 0 { 4 * n } else { 1 };
        let mut st = Self {
            n,
            tree: vec![0; tree_size],
            arr: slice.to_vec(),
        };

        if n > 0 {
            st.build(1, 0, n - 1);
        }
        st
    }

    fn build(&mut self, node: usize, start: usize, end: usize) {
        if start == end {
            self.tree[node] = self.arr[start];
            return;
        }

        let mid = start + (end - start) / 2;
        let left_child = 2 * node;
        let right_child = 2 * node + 1;

        self.build(left_child, start, mid);
        self.build(right_child, mid + 1, end);

        self.tree[node] = self.tree[left_child] + self.tree[right_child];
    }

    pub fn update(&mut self, idx: usize, val: i64) {
        if idx >= self.n {
            return;
        }
        self.arr[idx] = val;
        self.update_node(1, 0, self.n - 1, idx, val);
    }

    fn update_node(&mut self, node: usize, start: usize, end: usize, idx: usize, val: i64) {
        if start == end {
            self.tree[node] = val;
            return;
        }

        let mid = start + (end - start) / 2;
        let left_child = 2 * node;
        let right_child = 2 * node + 1;

        if idx <= mid {
            self.update_node(left_child, start, mid, idx, val);
        } else {
            self.update_node(right_child, mid + 1, end, idx, val);
        }

        self.tree[node] = self.tree[left_child] + self.tree[right_child];
    }

    pub fn query_sum(&self, ql: usize, qr: usize) -> i64 {
        if self.n == 0 || ql > qr || qr >= self.n {
            return 0;
        }
        self.query_node(1, 0, self.n - 1, ql, qr)
    }

    fn query_node(&self, node: usize, start: usize, end: usize, ql: usize, qr: usize) -> i64 {
        if ql <= start && end <= qr {
            return self.tree[node];
        }
        if end < ql || start > qr {
            return 0;
        }

        let mid = start + (end - start) / 2;
        let left_sum = self.query_node(2 * node, start, mid, ql, qr);
        let right_sum = self.query_node(2 * node + 1, mid + 1, end, ql, qr);

        left_sum + right_sum
    }
}

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

from typing import List


class SegmentTree:
    """Segment Tree canónico de sumas con arreglo plano de tamaño 4N."""

    def __init__(self, arr: List[int]) -> None:
        self.n = len(arr)
        self.arr = list(arr)
        self.tree = [0] * (4 * self.n if self.n > 0 else 1)
        if self.n > 0:
            self._build(1, 0, self.n - 1)

    def _build(self, node: int, start: int, end: int) -> None:
        if start == end:
            self.tree[node] = self.arr[start]
            return
        mid = (start + end) // 2
        lc, rc = 2 * node, 2 * node + 1
        self._build(lc, start, mid)
        self._build(rc, mid + 1, end)
        self.tree[node] = self.tree[lc] + self.tree[rc]

    def update(self, idx: int, val: int) -> None:
        self.arr[idx] = val
        self._update_node(1, 0, self.n - 1, idx, val)

    def _update_node(self, node: int, start: int, end: int, idx: int, val: int) -> None:
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self._update_node(2 * node, start, mid, idx, val)
        else:
            self._update_node(2 * node + 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, ql: int, qr: int) -> int:
        return self._query_node(1, 0, self.n - 1, ql, qr)

    def _query_node(self, node: int, start: int, end: int, ql: int, qr: int) -> int:
        if ql <= start and end <= qr:
            return self.tree[node]
        if end < ql or start > qr:
            return 0
        mid = (start + end) // 2
        return self._query_node(2 * node, start, mid, ql, qr) + self._query_node(2 * node + 1, mid + 1, end, ql, qr)

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: Arreglo de Tamaño 1: - Para arr = [42], verifica que st.query_sum(0, 0) retorne 42 y que tras st.update(0, 99), la consulta retorne 99 sin pánico de índice.
2. Paso Límite 2: Consulta del Arreglo Completo: - Para un arreglo de tamaño N, comprueba que st.query_sum(0, n - 1) se resuelva en un solo paso (O(1)), retornando directamente el valor de la raíz tree[1].
3. Paso Límite 3: Segment Tree de GCD (Máximo Común Divisor): - Modifica el combinador del Segment Tree para usar el algoritmo euclidiano de GCD. Demuestra cómo responde el máximo común divisor de cualquier subrango en O(log N · log(valor)).

Navegación final:

• ← Sesión 52: Árbol Binario Indexado (Fenwick Tree / BIT) y Prefijos Dinámicos
• Sesión 54: Algoritmo de Kadane: Máxima Submatriz y Variantes Circulares (CTCI 17.24) →
• Glosario Maestro
• Guía de Diagramas de Arquitectura