¿Cómo respondes rápido a muchas consultas de rango sum(nums[i:j]) sobre un array estático?
Opciones
- Recalcular cada suma al pedirla, O(n) por consulta
- Prefix sums: cada consulta es
p[j] - p[i](Opción correcta) - Ordenar el array una vez y luego cortar el rango
- Mantener una pila de sumas parciales por consulta
Respuesta
Precalcular prefix sums una vez (O(n)); cada consulta es prefix[j] - prefix[i] (O(1))
Por qué
Construye prefix, donde prefix[k] es la suma de los primeros k elementos. Esto requiere una pasada.
Luego la suma de cualquier rango i..j-1 es prefix[j] - prefix[i]: una resta.
Por ejemplo nums = [3, 1, 4]: prefix = [0, 3, 4, 8]; la suma de nums[1:3] = 8 - 3 = 5.
Recuerda
Muchas sumas de rango → prefix sums.