Sommare qualsiasi intervallo con una sottrazione
Rispondere a range[l..r] in tempo costante
Sommare qualsiasi intervallo con una sottrazione è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il vero vantaggio
La costruzione dell'array delle somme prefisse era solo la preparazione. Ora arriva la parte interessante: rispondere alla somma di qualsiasi intervallo con un'unica sottrazione. ⚡
L'idea fondamentale
La somma di un intervallo è semplicemente un totale grande meno uno più piccolo. Sottraendo due valori delle somme prefisse si annulla in modo preciso tutto ciò che si trova al di fuori dell'intervallo.
La formula
Per sommare gli elementi da l a r, calcoli prefix[r + 1] meno prefix[l]. Questa singola formula funziona per qualsiasi intervallo.
range_sum = prefix[r + 1] - prefix[l]Perché funziona
prefix[r + 1] contiene tutti gli elementi fino a r, mentre prefix[l] contiene tutti quelli precedenti a l. La differenza lascia esattamente la porzione centrale.
Un esempio svolto
Per [3, 1, 4], il prefisso è [0, 3, 4, 8]. Per sommare gli indici da 1 a 2, calcoli 8 meno 3, ottenendo 5. È proprio 1 più 4.
Query in tempo costante
Ogni query consiste in una sola sottrazione, quindi viene eseguita in O(1). Mille query hanno lo stesso costo per query di una sola.
Attenzione all'errore di uno
L'errore più comune riguarda l'indice dell'estremo superiore. Con uno zero iniziale, usi sempre prefix[r + 1], non prefix[r]. Faccia attenzione a questo limite.
Inclusivo o esclusivo
Decida subito se r è incluso. Questa formula considera l'intervallo inclusivo di entrambi gli estremi l e r, come richiesto dalla maggior parte dei problemi di programmazione competitiva.
Racchiuda tutto in una funzione
Una piccola funzione di supporto mantiene leggibile la logica e concentra gli indici in un unico punto. Si affidi a questa funzione di supporto invece di inserire i calcoli direttamente nel codice.
def query(l, r):
return prefix[r + 1] - prefix[l]Gestisca l'intero array
Per sommare l'intero array, usi l uguale a 0 e r uguale a n meno 1. La formula restituisce prefix[n], il totale complessivo.
Dove dà il meglio di sé
Ogni volta che un problema richiede molte query di somma su un intervallo di un array fisso, le somme prefisse trasformano un ciclo O(n) per query in risposte immediate.
Verifica rapida
Vuole calcolare la somma degli indici da l a r, inclusi.
Riepilogo
Ora può rispondere a qualsiasi query di somma su un intervallo in O(1), usando prefix[r + 1] meno prefix[l]. Faccia attenzione all'offset dovuto allo zero iniziale e non avrà bug. ✅
Domande Frequenti
La lezione «Sommare qualsiasi intervallo con una sottrazione» è gratuita?
Sì — il testo completo di «Sommare qualsiasi intervallo con una sottrazione» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sommare qualsiasi intervallo con una sottrazione»?
Rispondere a range[l..r] in tempo costante Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Sommare qualsiasi intervallo con una sottrazione»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Creare un array delle somme prefisse
- Sommare qualsiasi intervallo con una sottrazione
- Contare i sottoarray con una somma obiettivo
- Array delle differenze per aggiornamenti su intervalli