Range Sum Queries (Bereichssummenabfragen)
Du hast ein Array mit n Elementen sowie q Range Sum Queries (Bereichssummenabfragen). Deine Aufgabe besteht darin, jede dieser Abfragen effizient zu beantworten, indem du die Summe der Array-Elemente in dem angegebenen Bereich mithilfe einer Segment Tree (Segmentbaum)-Datenstruktur berechnest.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen n und q (1 ≤ n, q ≤ 100 000), die die Zahl der Elemente im Array und die Anzahl der Abfragen darstellen.
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (), die die Elemente des Arrays repräsentieren.
Die nächsten q Zeilen enthalten jeweils zwei ganze Zahlen und (), welche die Grenzen des Bereichs für die jeweilige Anfrage angeben.
Ausgabe
Für jede Abfrage soll die Summe der Elemente im angegebenen Bereich ausgegeben werden. Jede Summe steht in einer neuen Zeile.
Beispiele
Eingabe | Ausgabe |
5 3
1 2 3 4 5
1 3
2 4
1 5 | 6
9
15 |
Erklärung
Für das gegebene Array [1, 2, 3, 4, 5] werden folgende Bereichssummenabfragen durchgeführt:
- Abfrage [1, 3]: Die Summe der Elemente von Index 1 bis 3 beträgt 1 + 2 + 3 = 6.
- Abfrage [2, 4]: Die Summe der Elemente von Index 2 bis 4 beträgt 2 + 3 + 4 = 9.
- Abfrage [1, 5]: Die Summe der Elemente von Index 1 bis 5 beträgt 1 + 2 + 3 + 4 + 5 = 15.
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB