Bereichsabfragen
Angenommen, wir haben ein Array
a mit n Ganzzahlen. Ihre Aufgabe ist es, q Anfragen zu beantworten. Alle diese Anfragen lauten: „Wie hoch ist die Summe der Elemente im Array a zwischen den Indizes [l; r]?“ (beide Grenzen sind inklusive und die Indizes beginnen bei 0).Eingabe
Die erste Zeile enthält eine einzelne ganze Zahl
n – die Anzahl der Elemente im Array (1 ≤ n ≤ 1000). In der nächsten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen, welche die Elemente des Arrays darstellen.Anschließend folgt eine Zeile mit einer ganzen Zahl
q – der Anzahl an Anfragen (1 ≤ q ≤ 1000). In den nächsten q Zeilen befinden sich jeweils Anfragen in der Form .Ausgabe
Das Programm soll
q Zeilen ausgeben, in denen jeweils die Summe der Elemente im Array a zwischen den Indizes (einschließlich beider Endpunkte) steht.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: 1 MB