Module: Decomposizione delle radici


Problem

1 /6


Somma sul segmento - 1

Theory Click to read/hide

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.
 

Problem

Dato un array a di lunghezza n (\(1 <= n <= 2 \cdot 10^6\ ), \(1 <= a_i <= 10^9\)). Date anche m (\(1 <= m <= 500\)) query come l, r (\(1 <= l <= r <= n\)).

Per ogni query, stampa la somma dei numeri compresi tra l e r inclusi. Gli elementi sono numerati a partire da 1 a n.

 

Esempi
# Input Uscita
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!