Decomposizione delle radici

Abbiamo un problema su come calcolare rapidamente le somme sull'intervallo l...r in un array statico a in meno di O(n) asintotici.

Dividiamo l'array a in k blocchi della stessa dimensione e calcoliamo prima la somma degli elementi per ciascuno di essi.

Ora, quando rispondiamo alla richiesta, possiamo esaminare gli elementi dell'array a e aggiungerli al risultato, anche se uno dei blocchi si trova all'interno del segmento, allora possiamo aggiungere la sua somma al risultato e saltare il elementi di questo blocco.

Il numero massimo di operazioni per query con questo algoritmo è n / k + k, quindi il k ottimale è uguale alla radice quadrata di n.

 

Abbiamo un problema su come calcolare rapidamente le somme sul segmento l...r nell'array a, in cui gli elementi possono cambiare uno alla volta, in asintotici minori di O(n).

Questa attività viene risolta in modo simile alla precedente, ma quando richiedi una modifica, devi modificare l'importo nel blocco corrispondente.

Viene dato un compito in cui è necessario eseguire operazioni di massa su un segmento e riconoscere un elemento per indice.

Le operazioni di massa vengono eseguite come calcolo di somma su un segmento.

Per ogni blocco, memorizziamo la modifica in quel blocco e quando richiediamo un elemento da quel blocco, prendiamo in considerazione tali informazioni.