Una suma de prefijos guarda totales acumulados para que el total de cualquier rango se reduzca a una resta. Si prefix[i] es el total de los primeros i valores, el rango de left a right vale prefix[right + 1] - prefix[left]. El cero extra del principio permite que un rango empiece en el índice 0 sin tratarlo como caso especial.
Recurre a las sumas de prefijos cuando un problema hace muchas preguntas de rango sobre datos que no cambian, o cuando te pide contar los rangos que suman una cantidad. Para contar rangos se combinan con un mapa hash: un rango que termina aquí suma el objetivo cuando algún prefijo anterior vale el total actual menos el objetivo. Funciona con números negativos, donde una ventana deslizante no sabe cuándo encogerse.
Un array de diferencias aplica la idea al revés. En lugar de guardar valores, guarda dónde empieza y dónde termina cada cambio, y calcula una suma acumulada al final. El mismo truco de la resta se extiende a cuadrículas: una tabla de prefijos en 2D da el total de cualquier rectángulo con cuatro consultas.
El total de un rango es la diferencia entre dos sumas de prefijos.