Range Sum Query

Q: Che cos'è un array di somme prefisse?

È un array in cui ogni elemento è il totale di tutti i valori che precedono una posizione: prefix[i] = nums[0] + ... + nums[i-1] , con prefix[0] = 0 . Lo costruisci in un'unica passata e, successivamente, la somma di qualsiasi intervallo [left, right] è prefix[right+1] - prefix[left] , con una sola sottrazione.

Q: Qual è la complessità temporale delle query di somma su un intervallo con somme prefisse?

O(n) per costruire l’array dei prefissi una volta, poi O(1) per ogni query, quindi O(n + q) per q query. Sommare direttamente ogni intervallo costa fino a O(n) per query, ovvero O(n·q) in totale.

Q: Perché l’array dei prefissi ha un elemento in più rispetto a nums?

L'elemento aggiuntivo prefix[0] = 0 rappresenta l'inizio vuoto dell'array. Con questo, ogni intervallo usa la stessa formula, compresi gli intervalli che iniziano all'indice 0: prefix[right+1] - prefix[0] . Senza, hai bisogno di un ramo separato per left = 0 .

Q: Che succede se l'array può cambiare tra una query e l'altra?

Quindi, un array di prefissi non è lo strumento adatto, perché un aggiornamento sposta tutti i totali successivi e richiede O(n) per essere corretto. Un albero di Fenwick o un albero dei segmenti gestisce sia un aggiornamento sia una somma su un intervallo in O(log n) . Quando l’array non cambia mai, le somme prefisse semplici sono più veloci e concise.

FacileSomme prefisse

+10

Ricevi un array di numeri interi nums che non cambia mai e un elenco di queries. Ogni query è una coppia [left, right] di indici con base 0 e chiede di calcolare nums[left] + nums[left+1] + ... + nums[right], inclusi entrambi gli estremi. Restituisci le risposte nello stesso ordine delle query.

Funzione

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

numsinteger-array: l'array di numeri interi, lo stesso 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, una per query, nell’ordine delle query

Vincoli

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length per ogni query [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 valore 1.

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 2 + 7 + 1 + 8 = 18, gli ultimi due valori 1 + 8 = 9, solo l’indice 0 2 e gli indici da 1 a 2 7 + 1 = 8.

+14 test nascosti all’invio

Per approfondire

Ora i numeri formano una griglia e ogni query chiede la somma di un rettangolo definito da due angoli. Come estenderesti le somme prefisse per rispondere a ogni query con un numero costante di operazioni?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un intervallo è un ciclo. Il problema è il loro numero: ogni query può coprire gran parte dell'array, quindi sommarli uno per uno ripete le stesse somme più e più volte. Somma tutto una volta sola nei prefissi cumulativi e ogni intervallo diventa una sottrazione.

Somma ogni intervallo

Corretto, ma non termina sui test più grandi

Intuizione

Rispondi a ogni query separatamente: parti da un totale di 0, somma nums[left] fino a nums[right] e memorizza il risultato. Per [1, 4] in [3, -2, 5, 1, -4, 6] il calcolo è -2 + 5 + 1 + (-4) = 0.

È corretto e, per una singola query, è il meglio che puoi fare: devi leggere una volta ogni valore nell’intervallo. Il costo sta nella ripetizione. Una query può includere fino a n valori, quindi q query richiedono fino a n × q addizioni. Con n = 10^4 e 1500 query che coprono ciascuna gran parte dell’array, si tratta di circa 1.3 × 10^7 addizioni, quasi tutte ripetizioni di operazioni già svolte per una query precedente.

Oltre all’elenco delle risposte, mantiene un totale, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Crea una lista di risposte vuota.
Per ogni query [left, right], imposta total = 0.
Aggiungi nums[i] a total per ogni i da left a right, inclusi entrambi.
Aggiungi total alle 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 answers

Somme prefisse

Intuizione

Sia prefix[i] la somma dei primi i valori, con prefix[0] = 0 per l'inizio vuoto. Per [3, -2, 5, 1, -4, 6] si ottiene prefix = [0, 3, 1, 6, 7, 3, 9]. Ogni elemento è quello precedente più un valore, quindi l'intero array richiede n addizioni.

L'intervallo [left, right] è tutto fino all'indice right incluso, meno tutto ciò che precede l'indice left. Cioè prefix[right+1] - prefix[left]. Per [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Per [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. Lo 0 iniziale permette di gestire un intervallo che inizia all'indice 0 senza un caso speciale.

Costruire l'array costa O(n), e ogni query richiede poi una sottrazione, quindi il tempo totale è O(n + q) e lo spazio aggiuntivo è O(n). Nessuna somma prefissa supera 10^4 × 10^4 = 10^8, quindi sono sufficienti interi a 32 bit.

Algoritmo

Crea prefix di lunghezza n+1 con prefix[0] = 0.
Per ogni i da 0 a n-1, imposta prefix[i+1] = prefix[i] + nums[i].
Per ogni query [left, right], aggiungi prefix[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

Quasi tutti i bug qui sono dovuti a un indice spostato di uno.

Scrivere prefix[right] - prefix[left]. Con prefix[0] = 0, questo esclude nums[right], quindi l’intervallo [3, 3] restituisce 0 invece del valore all’indice 3.
Creare prefix con la stessa lunghezza di nums, così prefix[i] include nums[i]. In tal caso, per un intervallo che inizia da 0 serve prefix[left-1], che è fuori dai limiti e, in Python, legge silenziosamente l’ultimo elemento. Lo 0 iniziale aggiuntivo elimina questo caso particolare.
Fermare la forza bruta a i < right. Entrambi gli estremi dell’intervallo sono inclusi.
Dimenticare che Lua e R iniziano a contare da 1. L’interrogazione basata su 0 [left, right] copre nums[left+1] fino a nums[right+1] e anche la differenza dei prefissi si sposta allo stesso modo.
Usare un totale a 32 bit quando i valori o le lunghezze aumentano. Qui la somma massima è 10^8, ma con valori vicini a 10^9 una somma prefissa va rapidamente in overflow, e un array a 64 bit è la scelta predefinita più sicura.

Domande frequenti4

Che cos'è un array di somme prefisse?

È un array in cui ogni elemento è il totale di tutti i valori che precedono una posizione: prefix[i] = nums[0] + ... + nums[i-1], con prefix[0] = 0. Lo costruisci in un'unica passata e, successivamente, la somma di qualsiasi intervallo [left, right] è prefix[right+1] - prefix[left], con una sola sottrazione.

Qual è la complessità temporale delle query di somma su un intervallo con somme prefisse?

O(n) per costruire l’array dei prefissi una volta, poi O(1) per ogni query, quindi O(n + q) per q query. Sommare direttamente ogni intervallo costa fino a O(n) per query, ovvero O(n·q) in totale.

Perché l’array dei prefissi ha un elemento in più rispetto a nums?

L'elemento aggiuntivo prefix[0] = 0 rappresenta l'inizio vuoto dell'array. Con questo, ogni intervallo usa la stessa formula, compresi gli intervalli che iniziano all'indice 0: prefix[right+1] - prefix[0]. Senza, hai bisogno di un ramo separato per left = 0.

Che succede se l'array può cambiare tra una query e l'altra?

Quindi, un array di prefissi non è lo strumento adatto, perché un aggiornamento sposta tutti i totali successivi e richiede O(n) per essere corretto. Un albero di Fenwick o un albero dei segmenti gestisce sia un aggiornamento sia una somma su un intervallo in O(log n). Quando l’array non cambia mai, le somme prefisse semplici sono più veloci e concise.

Python

def sumRange(nums, queries):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso

[6, 0, 1]