Árbol de Fenwick y segment tree

Las sumas acumuladas resuelven las consultas por rango en $O(1)$ con una condición: que los datos no cambien. Cuando cambian, cada modificación obliga a recalcular todo lo que sigue y la ventaja desaparece.

La salida es guardar sumas parciales en forma de árbol, en vez de sumas totales en forma de arreglo. Ninguna posición guarda el total hasta ella; cada una guarda el total de un bloque. Así, modificar toca unos pocos bloques y consultar combina unos pocos bloques: $O(\log n)$ las dos.

Cuál de las tres

Fenwick: el arreglo que se lee en binario

El árbol de Fenwick vive dentro de un arreglo común, indexado desde 1. Cada posición $i$ guarda la suma de un bloque que termina en $i$ y cuyo largo es el último bit encendido de $i$:

Esa operación —el bit menos significativo que está en uno— es todo el mecanismo. Para consultar el prefijo hasta $i$ se suma el bloque de $i$ y se salta al que termina antes, apagando ese bit. Para modificar la posición $i$ se actualiza su bloque y se salta al bloque que lo contiene, sumando ese bit.

class FenwickTree {
  private readonly sums: number[];

  constructor(size: number) {
    this.sums = new Array<number>(size + 1).fill(0);
  }

  /** Suma delta a la posición index, contada desde cero. */
  add(index: number, delta: number): void {
    for (let cursor = index + 1; cursor < this.sums.length; cursor += cursor & -cursor) {
      this.sums[cursor] += delta;
    }
  }

  /** Suma de las posiciones 0 hasta index, inclusive. */
  prefixSum(index: number): number {
    let total = 0;
    for (let cursor = index + 1; cursor > 0; cursor -= cursor & -cursor) {
      total += this.sums[cursor];
    }
    return total;
  }

  rangeSum(from: number, to: number): number {
    return this.prefixSum(to) - (from === 0 ? 0 : this.prefixSum(from - 1));
  }
}

Segment tree: cada nodo es un bloque

El segment tree es más literal: la raíz cubre el arreglo entero, cada nodo parte su rango en dos mitades y las hojas son los elementos. Cada nodo guarda el resultado de la operación sobre su bloque.

La consulta se apoya en una idea sola: si el rango del nodo entra entero en el rango consultado, se devuelve su valor sin bajar más. Un rango cualquiera se descompone en $O(\log n)$ nodos completos.

Modificar rangos: propagación diferida

«Sumale 5 a todo el rango 100..250» sobre un segment tree común cuesta tocar cada hoja: $O(n)$. La propagación diferida arregla eso con una idea perezosa: anotar la modificación en el nodo que cubre el rango y no bajarla hasta que alguien pase por ahí.

Dónde aparece esto fuera de los ejercicios

Cierre