Range Sum Query

Q: ¿Qué es un arreglo de sumas de prefijos?

Un arreglo donde 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 sola pasada, y después la suma de cualquier rango [left, right] es prefix[right+1] - prefix[left] .

Q: ¿Cuál es la complejidad temporal de las consultas de suma de rangos con sumas de prefijos?

O(n) para construir 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, O(n·q) en total.

Q: ¿Qué pasa si el arreglo puede cambiar entre consultas?

Entonces, un arreglo de prefijos es la herramienta equivocada, porque una actualización desplaza todos los totales posteriores y cuesta O(n) repararlos. Un árbol Fenwick o un árbol de segmentos permite realizar tanto una actualización como una suma en un rango en O(log n) .

FácilSuma de prefijos

+10

Recibes un arreglo de enteros nums que nunca cambia y una lista de queries. Cada consulta es un par [left, right] de índices basados en 0, y solicita nums[left] + nums[left+1] + ... + nums[right], incluidos ambos extremos. Devuelve las respuestas en el mismo orden que las consultas.

Función

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: el arreglo de enteros, el mismo para cada consulta
queriesinteger-2d-array: los intervalos que hay que sumar, cada uno 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 ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length for every query [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 único 1.

Entrada: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
Salida: [18, 9, 2, 8]
Explicación: La suma de todo el arreglo es 18, la de los dos últimos valores es 1 + 8 = 9, la del índice 0 por sí solo es 2 y la de los índices del 1 al 2 es 7 + 1 = 8.

Para ir más allá

Si los números forman una cuadrícula y cada consulta pide la suma de un rectángulo, ¿cómo ampliarías las sumas de prefijos para responder cada consulta en tiempo constante?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un solo rango es un bucle, pero cada consulta puede abarcar la mayor parte del arreglo, así que sumar cada uno por separado repite las mismas sumas. Suma el arreglo una vez para obtener las 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

Para cada consulta, suma nums[left] hasta nums[right] a un total. Es correcto porque lee todos los valores del rango, y para una consulta eso es lo mejor que puedes hacer. Una consulta puede abarcar hasta n valores, así que q consultas cuestan hasta n × q sumas: 1.5 × 10^7 cuando n = 10^4 y q = 1500, casi todas repetidas.

Algoritmo

Crea una lista de respuestas vacía.
Para cada consulta [left, right], establece total = 0.
Suma nums[i] a total por cada i desde left hasta right, ambos incluidos.
Añade total a 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 answers

Sumas de prefijos

Intuición

Sea prefix[i] la suma de los primeros i valores, con prefix[0] = 0. Para [3, -2, 5, 1, -4, 6], eso da [0, 3, 1, 6, 7, 3, 9].

El rango [left, right] es todo lo que hay hasta el índice right menos todo lo que hay antes del índice left: prefix[right+1] - prefix[left]. Para [1, 4], eso es prefix[5] - prefix[1] = 3 - 3 = 0. El 0 inicial permite que un rango que empieza en el índice 0 use la misma fórmula. Una pasada de n sumas construye el arreglo, y cada consulta es entonces una resta.

Algoritmo

Crea prefix de longitud n+1 con prefix[0] = 0.
Para cada i desde 0 hasta n-1, establece prefix[i+1] = prefix[i] + nums[i].
Para cada consulta [left, right], añade prefix[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

Escribir prefix[right] - prefix[left]. Con prefix[0] = 0, eso deja fuera nums[right], así que el rango [3, 3] devuelve 0 en lugar de 1.
Hacer que prefix tenga la misma longitud que nums, de modo que prefix[i] incluya nums[i]. Entonces, un rango que empieza en 0 necesita prefix[-1], que está fuera de los límites, y Python lee silenciosamente la última entrada en su lugar.
Detener el bucle de fuerza bruta en i < right. Se incluyen ambos extremos, así que [3, 3] no sumaría nada.
En Lua y R, que empiezan a contar desde 1, la consulta basada en índices desde 0 [left, right] abarca desde nums[left+1] hasta nums[right+1], y los índices del prefijo se desplazan de la misma manera.

Preguntas frecuentes3

¿Qué es un arreglo de sumas de prefijos?

Un arreglo donde 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 sola pasada, y después la suma de cualquier rango [left, right] es prefix[right+1] - prefix[left].

¿Cuál es la complejidad temporal de las consultas de suma de rangos con sumas de prefijos?

O(n) para construir 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, O(n·q) en total.

¿Qué pasa si el arreglo puede cambiar entre consultas?

Entonces, un arreglo de prefijos es la herramienta equivocada, porque una actualización desplaza todos los totales posteriores y cuesta O(n) repararlos. Un árbol Fenwick o un árbol de segmentos permite realizar tanto una actualización como una suma en un rango en O(log n).

def sumRange(nums, queries):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumentos

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

Salida Esperada

[6, 0, 1]