Query di somma su intervalli 2
Si dispone di un array di
n elementi e di q query. Esistono due tipi di query:- Calcolare la somma degli elementi in un intervallo specifico.
- Aggiornare il valore di un elemento dell’array in una determinata posizione.
Il tuo obiettivo è gestire queste query in modo efficiente.
Input
La prima riga dell'input contiene due interi
n e q (1 ≤ n, q ≤ 100 000), che rappresentano rispettivamente il numero di elementi dell'array e il numero di query.La seconda riga contiene
n interi separati da spazio: (), che costituiscono il contenuto iniziale dell’array.Le successive
q righe descrivono una query ciascuna:- Per le query sulla somma di un intervallo: la riga inizia con
1, seguito da due interi e (), che indicano l’intervallo[ $$l_i, r_i$$ ]per il quale è necessario calcolare la somma.
- Per le query di aggiornamento: la riga inizia con
2, seguito da due interi e (), che rappresentano l’indice dell’elemento da modificare e il nuovo valore .
Output
Per ogni query che richiede la somma di un intervallo, stampa su una riga separata la somma dei valori compresi nell’intervallo specificato.
Esempi
Ingresso | Uscita |
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