Module: Decomposizione delle radici


Problem

3 /6


Somma sul segmento - 2

Theory Click to read/hide

Abbiamo un problema su come calcolare rapidamente le somme sul segmento l...r nell'array a, in cui gli elementi possono cambiare uno alla volta, in asintotici minori di O(n).
Questa attività viene risolta in modo simile alla precedente, ma quando richiedi una modifica, devi modificare l'importo nel blocco corrispondente.

Problem

Dato un array a di lunghezza n (\(1 <= n <= 2 \cdot 10^6\ ), \(1 <= a_i <= 10^9\)). Date anche m (\(1 <= m <= 500\)) query come t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Se \(t = 0\), la query dovrebbe visualizzare la somma dei numeri nel segmento da l code> a r inclusi. Se \(t = 1\), allora il numero dell'elemento l è impostato su r. Gli elementi sono numerati da 1 a n. 

 

Esempi
# Input Uscita
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!