Query di somma su intervalli (Range Sum Queries)
Ti viene fornito un array di
n elementi e q query di somma su intervalli. Il tuo compito è rispondere in modo efficiente a ciascuna query, calcolando la somma degli elementi compresi in un determinato intervallo, utilizzando una struttura dati di tipo Segment Tree.Input
La prima riga dell’input contiene due interi
n e q (1 ≤ n, q ≤ 100 000), che rappresentano rispettivamente il numero di elementi nell’array e il numero di query.La seconda riga contiene
n interi separati da spazio (), ossia gli elementi dell’array.Le successive
q righe contengono ciascuna due interi e () che indicano l’intervallo per ogni query.Output
Per ogni query, stampa la somma degli elementi compresi nell’intervallo indicato, ciascuna su una nuova riga.
Esempi
Ingresso | Uscita |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Spiegazione
Per l’array
[1, 2, 3, 4, 5], eseguiamo le seguenti query di somma su intervalli:- Query
[1, 3]: la somma degli elementi da 1 a 3 è 1 + 2 + 3 = 6.
- Query
[2, 4]: la somma degli elementi da 2 a 4 è 2 + 3 + 4 = 9.
- Query
[1, 5]: la somma degli elementi da 1 a 5 è 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB