Lascia che ci sia un array. In assenza di modifiche, possiamo rapidamente (più velocemente di una riga) trovare il valore di alcune funzioni su un sottosegmento di questo array. Per fare ciò, dobbiamo utilizzare memoria aggiuntiva ed eseguire un pre-calcolo.
Ad esempio, dobbiamo trovare rapidamente la somma su un segmento dell'array.
Otteniamo un array di somme di prefissi, in cui l'indice i sarà la somma di tutti gli elementi dell'array con indici minori o uguali a i.
a[] – dato array, p[] – matrice di somme di prefissi
Conteggio array p:
Ovviamente p[0] = a[0]. Nota che possiamo facilmente ricalcolare p[i] tramite p[i – 1], perché l'importo sul prefisso i è l'importo sul prefisso i – 1 + a[i].
Pertanto, il codice per calcolare le somme dei prefissi è simile al seguente:
int a[n], p[n];
p[0] = a[0< /span>];
per (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Inoltre, notiamo che la somma sul segmento – la differenza tra le due somme sul prefisso.
Verde = rosso – blu
Quindi, se è necessario trovare la somma sull'intervallo [l,r], allora la risposta è p[r] – p[l-1].
Tuttavia, se l – 1 elemento potrebbe non esistere. Per fare a meno degli if, puoi inserire 1-indicizzazione, e a[0] e p[0] avranno valori neutri (0 per la somma).
Si noti che questa tecnica è un caso particolare della formula di inclusione-esclusione, quindi in questo modo è possibile memorizzare non solo somme, ma anche altre funzioni, come la moltiplicazione e xor.