Complejidad Temporal
O(n)
Un Prefix Sum Array preprocesa un arreglo estático para que las consultas de suma por rango sean O(1). Cada posición guarda la suma de todos los elementos hasta ese índice.
Cómo funciona:
1. Construir prefix[0] = arr[0]
2. Para cada índice siguiente, sumar el valor actual al prefijo anterior
3. Responder sum(l, r) con prefix[r] - prefix[l - 1]
4. Si l = 0, la respuesta es simplemente prefix[r]
Complejidad Temporal: O(n) de preprocesamiento, O(1) por consulta
Complejidad Espacial: O(n)
Conviene cuando:
- El arreglo es estático
- Necesitas muchas consultas de suma por rango
- Quieres cambiar una pasada de preprocesamiento por consultas instantáneas
Limitación:
- Las actualizaciones puntuales no se manejan eficientemente aquí; para actualizaciones dinámicas hacen falta otras estructuras como Fenwick Tree o Segment Tree.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Prefix Sum Array?
- Un Prefix Sum Array preprocesa un arreglo estático para que las consultas de suma por rango sean O(1). Cada posición guarda la suma de todos los elementos hasta ese índice.
- ¿Cuál es la complejidad de Prefix Sum Array?
- Tiempo (promedio): O(n) · Espacio: O(n)
- ¿Para quién es este visualizador de Prefix Sum Array?
- La visualización de Prefix Sum Array está pensada para nivel principiante, dentro de la categoría Conceptos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Prefix Sum Array?
- En la misma categoría (Conceptos) puedes explorar: Big O Notation, Recursion, Two Pointers. Todos tienen visualización interactiva.