Bereichssummen-Abfragen 2
Du hast ein Array mit
n Elementen und q Abfragen gegeben. Es gibt zwei Arten von Abfragen:- Bestimme die Summe eines bestimmten Bereichs
- Aktualisiere ein Element im Array an der angegebenen Position
Deine Aufgabe ist es, diese Abfragen effizient zu verarbeiten.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und q (1 ≤ n, q ≤ 100 000). Sie repräsentieren die Anzahl der Elemente im Array sowie die Anzahl der Abfragen.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (), die die anfänglichen Werte des Arrays darstellen.Die folgenden
q Zeilen stehen jeweils für eine Abfrage:- Bei einer Bereichssummen-Abfrage beginnt die Zeile mit der Zahl
1, gefolgt von den zwei ganzzahligen Werten und (). Diese geben den Indexbereich[ $$l_i, r_i$$ ]an, über den die Summe der Elemente berechnet werden soll.
- Bei einer Aktualisierungs-Abfrage beginnt die Zeile mit der Zahl
2, gefolgt von den zwei ganzzahligen Werten und (). Dabei gibt die zu ändernde Position im Array an, und ist der neue Wert.
Ausgabe
Gib für jede Bereichssummen-Abfrage die Summe der Werte in dem entsprechenden Bereich in einer eigenen Zeile aus.
Beispiele
Eingabe | Ausgabe |
5 3
1 2 3 4 5
1 1 3
1 2 4
1 1 5 | 6
9
15 |
5 3
1 2 3 4 5
1 1 3
2 1 5
1 1 5 | 6
19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB