Module: Wurzeldekomposition


Problem

3 /6


Die Summe pro Strecke beträgt 2

Theory Click to read/hide

Wir haben eine Aufgabe, schnell die Beträge auf dem l...r in einer Masse a zu betrachten, wo die Elemente eine nach einem ändern können, für asymptotisch weniger als O(n).
Diese Aufgabe wird ähnlich wie die vorangegangene durchgeführt, jedoch ist es im Antrag auf Änderung erforderlich, den Betrag in der entsprechenden Einheit zu ändern.

Problem

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n. 

 

Примеры
№ Входные данные Выходные данные
1
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
 3
7
5

time 3000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!