Range Sum Query
Recibes un arreglo de números enteros nums que nunca cambia y una lista de queries. Cada consulta es un par [left, right] de índices basados en 0, y pide nums[left] + nums[left+1] + ... + nums[right], incluidos ambos extremos. Devuelve las respuestas en el mismo orden que las consultas.
Función
- numsinteger-array
- el arreglo de enteros, el mismo para cada consulta
- queriesinteger-2d-array
- los intervalos que se deben sumar, cada uno es un par [left, right] con left ≤ right
- Devuelveinteger-array
- la suma de cada rango, una por consulta, en el orden de las consultas
Restricciones
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthpara cada consulta[left, right]
Ejemplos
- Entrada
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Salida
- [6, 0, 1]
- Explicación
- Los índices del 0 al 2 contienen
3 + (-2) + 5 = 6. Los índices del 1 al 4 contienen-2 + 5 + 1 + (-4) = 0. El rango[3, 3]es el valor único1.
- Entrada
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Salida
- [18, 9, 2, 8]
- Explicación
- El array completo suma
2 + 7 + 1 + 8 = 18, los dos últimos valores suman1 + 8 = 9, solo el índice 0 suma2y los índices del 1 al 2 suman7 + 1 = 8.
+14 pruebas ocultas al enviar
Para ir más allá
Ahora los números forman una cuadrícula, y cada consulta pide la suma de un rectángulo definido por dos esquinas. ¿Cómo ampliarías las sumas de prefijos para responder cada consulta con una cantidad constante de operaciones?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Muchas consultas abarcan casi los mismos valores. ¿Qué trabajo podrías hacer una sola vez, antes de leer cualquier consulta?
Si conocieras el total de los primeros
ivalores para cadai, un rango sería la diferencia entre dos de esos totales.Construye
prefixconprefix[0] = 0yprefix[i+1] = prefix[i] + nums[i]. Después, cada consulta[left, right]esprefix[right+1] - prefix[left].
Solución
Un rango es un bucle. El problema es la cantidad de rangos: cada consulta puede abarcar la mayor parte del arreglo, así que sumar cada uno por separado repite las mismas sumas una y otra vez. Súmalo todo una vez en sumas de prefijos y cada rango se convierte en una resta.
Suma cada rango
Correcto, pero no termina con las pruebas más grandes
Intuición
Responde cada consulta por separado: empieza con un total de 0, suma nums[left] hasta nums[right] y guarda el resultado. Para [1, 4] en [3, -2, 5, 1, -4, 6], el resultado es -2 + 5 + 1 + (-4) = 0.
Es correcto y, para una sola consulta, es lo mejor que puedes hacer: tienes que leer cada valor del rango una vez. El coste está en la repetición. Una consulta puede abarcar hasta n valores, así que q consultas cuestan hasta n × q sumas. Con n = 10^4 y 1500 consultas que abarcan cada una la mayor parte del array, son aproximadamente 1.3 × 10^7 sumas, casi todas repeticiones de trabajo realizado para una consulta anterior.
Además de la lista de respuestas, mantiene un total, así que el espacio adicional es O(1).
Algoritmo
- Crea una lista de respuestas vacía.
- Para cada consulta
[left, right], establecetotal = 0. - Suma
nums[i]atotalpor cadaidesdelefthastaright, ambos incluidos. - Añade
totala las respuestas y devuélvelas después de la última consulta.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersSumas de prefijos
Intuición
Sea prefix[i] la suma de los primeros i valores, con prefix[0] = 0 para el inicio vacío. Para [3, -2, 5, 1, -4, 6], eso da prefix = [0, 3, 1, 6, 7, 3, 9]. Cada elemento es el anterior más un valor, así que el array completo requiere n sumas.
El rango [left, right] incluye todo hasta el índice right, menos todo lo que está antes del índice left. Es decir, prefix[right+1] - prefix[left]. Para [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Para [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. El 0 inicial es lo que permite que funcione un rango que empieza en el índice 0 sin un caso especial.
Construir el array cuesta O(n), y cada consulta cuesta una resta, así que el tiempo total es O(n + q) y el espacio adicional es O(n). Ninguna suma de prefijos supera 10^4 × 10^4 = 10^8, así que los enteros de 32 bits son suficientes.
Algoritmo
- Crea
prefixde longitudn+1conprefix[0] = 0. - Para cada
idesde0hastan-1, estableceprefix[i+1] = prefix[i] + nums[i]. - Para cada consulta
[left, right], añadeprefix[right+1] - prefix[left]a las respuestas. - Devuelve las respuestas.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Errores comunes y casos límite
Casi todos los errores aquí se deben a un índice desplazado en una posición.
- Escribir
prefix[right] - prefix[left]. Conprefix[0] = 0, se omitenums[right], así que el rango[3, 3]devuelve0en vez del valor en el índice 3. - Construir
prefixcon la misma longitud quenums, de modo queprefix[i]incluyanums[i]. Después, un rango que empieza en0necesitaprefix[left-1], que está fuera de los límites, y en Python lee silenciosamente la última entrada. El0inicial adicional elimina ese caso especial. - Detener la fuerza bruta en
i < right. Se incluyen ambos extremos del rango. - Olvidar que Lua y R cuentan desde 1. Allí, la consulta con índices desde 0
[left, right]abarca desdenums[left+1]hastanums[right+1], y la diferencia de prefijos se desplaza del mismo modo. - Usar un total de 32 bits cuando aumentan los valores o las longitudes. Aquí la suma máxima es
10^8, pero con valores cercanos a10^9, una suma de prefijos se desborda rápidamente, y un arreglo de 64 bits es la opción segura predeterminada.
Preguntas frecuentes4
¿Qué es un arreglo de sumas prefijas?
Es un arreglo en el que cada entrada es el total de todos los valores anteriores a una posición: prefix[i] = nums[0] + ... + nums[i-1], con prefix[0] = 0. Lo construyes en una pasada y, después, la suma de cualquier intervalo [left, right] es prefix[right+1] - prefix[left], una resta.
¿Cuál es la complejidad temporal de las consultas de suma en un rango con sumas de prefijos?
O(n) para crear el arreglo de prefijos una vez, después O(1) por consulta, así que O(n + q) para q consultas. Sumar directamente cada rango cuesta hasta O(n) por consulta, lo que da O(n·q) en total.
¿Por qué el arreglo de prefijos tiene una entrada más que nums?
El prefix[0] = 0 adicional representa el inicio vacío del array. Con él, todos los rangos usan la misma fórmula, incluidos los rangos que empiezan en el índice 0: prefix[right+1] - prefix[0]. Sin él, necesitas una rama aparte para left = 0.
¿Qué pasa si la matriz puede cambiar entre consultas?
Entonces, un arreglo de prefijos no es la herramienta adecuada, porque una actualización desplaza todos los totales posteriores y cuesta O(n) repararla. Un árbol de Fenwick o un árbol de segmentos gestiona tanto una actualización como una suma de rango en O(log n). Cuando el arreglo nunca cambia, las sumas de prefijos simples son más rápidas y concisas.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def sumRange(nums, queries):
# Escribe el código aquíCaso 1
Caso 2
Entrada
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Esperado
[6, 0, 1]