¿Qué es una suma de prefijos (prefix sum) y cómo acelera las consultas de rango?

Question

Accepted Answer

Un arreglo de **suma de prefijos** almacena totales acumulativos de modo que cualquier **suma de rango** puede responderse en **O(1)** después de O(n) preprocesamiento — en lugar de O(n) por consulta.

## La idea

Sea `prefix[i]` la suma de los primeros `i` elementos. Entonces la suma de `arr[l..r]` es `prefix[r+1] - prefix[l]`.

## Ejemplo

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Seguimiento

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Complejidad

- **Construcción:** O(n). **Consulta:** O(1). **Espacio:** O(n).

## Cuándo usar / Trampas

Ideal para **muchas consultas de suma de rango** en datos estáticos. Variantes: sumas de prefijos 2D para sumas de submatrices, XOR de prefijos y arreglos de diferencias para actualizaciones de rango. Si el arreglo cambia a menudo, use un árbol Fenwick/segment en su lugar. Cuidado con el desplazamiento de índice (tamaño n+1).

## Por qué es importante

Las sumas de prefijos convierten consultas de rango O(n) repetidas en búsquedas O(1) — una gran ganancia cuando las consultas son frecuentes.

El patrón de precalcular una vez y responder rápido se generaliza a muchas tareas de procesamiento de datos.

Es un pilar de la programación competitiva y un componente construccional común en análisis.