Range Sum Query
Ricevi un array di numeri interi nums che non cambia mai e un elenco di queries. Ogni query è una coppia [left, right] di indici a partire da 0 e richiede nums[left] + nums[left+1] + ... + nums[right], inclusi entrambi gli estremi. Restituisci le risposte nello stesso ordine delle query.
Funzione
- numsinteger-array
- l'array di interi, uguale per ogni query
- queriesinteger-2d-array
- gli intervalli da sommare, ciascuno una coppia [left, right] con left ≤ right
- Restituisceinteger-array
- la somma di ciascun intervallo, uno per query, nell'ordine delle query
Vincoli
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthper ogni richiesta[left, right]
Esempi
- Input
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Output
- [6, 0, 1]
- Spiegazione
- Gli indici da 0 a 2 contengono
3 + (-2) + 5 = 6. Gli indici da 1 a 4 contengono-2 + 5 + 1 + (-4) = 0. L’intervallo[3, 3]è il singolo valore1.
- Input
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Output
- [18, 9, 2, 8]
- Spiegazione
- L'intero array totalizza
18, gli ultimi due valori1 + 8 = 9, il solo indice 02e gli indici da 1 a 27 + 1 = 8.
Per approfondire
Se i numeri formano una griglia e ogni query chiede la somma di un rettangolo, come estenderesti le somme prefisse per rispondere a ogni query in tempo costante?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Molte query riguardano valori quasi identici. Quale lavoro potresti fare una sola volta, prima di leggere qualsiasi query?
Se conoscessi il totale dei primi
ivalori per ognii, un intervallo sarebbe la differenza tra due di quei totali.Costruisci
prefixconprefix[0] = 0eprefix[i+1] = prefix[i] + nums[i]. Poi ogni query[left, right]èprefix[right+1] - prefix[left].
Soluzione
Un singolo intervallo è un ciclo, ma ogni query può coprire la maggior parte dell'array, quindi sommarli uno per uno ripete le stesse addizioni. Somma una volta l'intero array nei prefissi, così ogni intervallo richiede una sola sottrazione.
Somma ogni intervallo
Corretto, ma non termina sui test più grandi
Intuizione
Per ogni query, aggiungi nums[left] fino a nums[right] a un totale. È corretto perché legge ogni valore nell’intervallo, e per una query è il meglio che puoi fare. Una query può comprendere fino a n valori, quindi q query richiedono fino a n × q addizioni: 1.5 × 10^7 quando n = 10^4 e q = 1500, quasi tutte ripetizioni.
Algoritmo
- Crea un elenco di risposte vuoto.
- Per ogni query
[left, right], impostatotal = 0. - Aggiungi
nums[i]atotalper ogniidaleftaright, estremi inclusi. - Aggiungi
totalalle risposte e restituiscile dopo l'ultima query.
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 answersSomme prefisse
Intuizione
Sia prefix[i] la somma dei primi i valori, con prefix[0] = 0. Per [3, -2, 5, 1, -4, 6] si ottiene [0, 3, 1, 6, 7, 3, 9].
L'intervallo [left, right] comprende tutti gli elementi fino all'indice right meno tutti quelli prima dell'indice left: prefix[right+1] - prefix[left]. Per [1, 4] è prefix[5] - prefix[1] = 3 - 3 = 0. Lo 0 iniziale permette a un intervallo che parte dall'indice 0 di usare la stessa formula. Una sola passata di n addizioni costruisce l'array, e ogni query richiede poi una sola sottrazione.
Algoritmo
- Crea
prefixdi lunghezzan+1conprefix[0] = 0. - Per ogni
ida0an-1, impostaprefix[i+1] = prefix[i] + nums[i]. - Per ogni query
[left, right], aggiungiprefix[right+1] - prefix[left]alle risposte. - Restituisci le risposte.
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]
Trappole e casi limite
- Scrivere
prefix[right] - prefix[left]. Conprefix[0] = 0, questo escludenums[right], quindi l’intervallo[3, 3]restituisce0invece di1. - Creare
prefixdella stessa lunghezza dinums, così cheprefix[i]includanums[i]. Un intervallo che inizia da 0 richiede quindiprefix[-1], che è fuori dai limiti, e Python legge silenziosamente l’ultima voce. - Fermare il ciclo di forza bruta a
i < right. Sono inclusi entrambi gli estremi, quindi[3, 3]non sommerebbe nulla. - In Lua e R, che contano a partire da 1, la query basata su indici da 0
[left, right]coprenums[left+1]fino anums[right+1], e gli indici del prefisso si spostano allo stesso modo.
Domande frequenti3
Che cos'è un array di somme prefisse?
Un array in cui ogni elemento è il totale di tutti i valori precedenti a una posizione: prefix[i] = nums[0] + ... + nums[i-1], con prefix[0] = 0. Lo costruisci in un'unica passata e poi la somma di qualsiasi intervallo [left, right] è prefix[right+1] - prefix[left].
Qual è la complessità temporale delle query di somma su intervalli con somme prefisse?
O(n) per costruire una volta l'array dei prefissi, poi O(1) per query, quindi O(n + q) per q query. Sommare direttamente ogni intervallo costa fino a O(n) per query, O(n·q) in totale.
E se l’array può cambiare tra una query e l’altra?
Quindi un array di prefissi è lo strumento sbagliato, perché un aggiornamento sposta tutti i totali successivi e costa O(n) ripristinarli. Un albero di Fenwick o un albero dei segmenti gestisce sia un aggiornamento sia una somma su un intervallo in O(log n).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def sumRange(nums, queries):
# Scrivi il codice quiTest #1
Test #2
Argomenti
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Output atteso
[6, 0, 1]