Schnellere Bereichsabfragen
Angenommen, wir haben ein Array
a mit n Ganzzahlen. Die Aufgabe besteht darin, q Abfragen zu beantworten. Alle Abfragen lauten: „Wie hoch ist die Summe der Elemente im Array a zwischen den Indizes [l; r]?“ (beide Endpunkte sind inklusive, und die Indizes beginnen bei 0). Dieses Mal sind sowohl die Zahl der Abfragen als auch die Größe des Arrays deutlich größer. Kannst du dir eine Methode überlegen, um diese Abfragen schneller zu bearbeiten?Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n – die Anzahl der Elemente im Array (1 ≤ n ≤ 10^5).In der nächsten Zeile folgen
n durch Leerzeichen getrennte Ganzzahlen, welche die Elemente des Arrays darstellen (-10^9 < a_i < 10^9).Ausgabe
Das Programm soll
q Zeilen ausgeben. In jeder Zeile steht die Summe der Array-Elemente a zwischen den Indizes [l_j, r_j] (beide inklusive).Beispiele
Eingabe | Ausgabe |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 25 MB