Range Sum 2

Du får givet en lista med $N$ heltal $A_0, A_1, \dots , A_{N-1}$.

Du måste hantera $Q$ stycken frågor av två typer:

• Typ 1: givet heltalen $l$ och $r$, skriv ut summan av talen i intervallet $[l,r]$, det vill säga $A_l + A_{l+1} + \dots + A_r$.

• Typ 2: givet heltalen $x$ och $y$, sätt $A_x = y$.

Indata

Den första raden innehåller två heltal $N, Q$ ($1 \leq N \leq 3 \cdot 10^5$, $1 \leq Q \leq 10^5$).

Nästa rad innehåller $N$ positiva heltal $A_0, A_1, \dots , A_{N-1}$ ($1 \leq A_i \leq 10^9$), den givna listan.

Därefter följer $Q$ rader som vardera innehåller en fråga. Varje fråga börjar med talet $T$ ($T \in \{ 1,2\} $).

Om $T=1$ följer heltalen $l, r$ ($0 \leq l \leq r < N$). I detta fall ska du skriva ut summan av talen i intervallet $[l,r]$.

Om $T=2$ följer heltalen $x$ och $y$ ($0 \leq x < N$, $1 \leq y \leq 10^9$). I detta fall ska du sätta $A_x = y$.

Utdata

För varje fråga med $T=1$, skriv ut summan i det efterfrågade intervallet.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

5 3
1 4 3 1 2
1 0 3
2 1 3
1 0 3

9
8