Consultas de Suma de Rangos 2
Se te da un arreglo de
n elementos y q consultas. Existen dos tipos de consultas:- Obtener la suma de un rango específico
- Actualizar el elemento del arreglo en la posición dada
Tu tarea es procesar estas consultas de manera eficiente.
Entrada
La primera línea de la entrada contiene dos enteros
n y q (1 ≤ n, q ≤ 100 000), que representan la cantidad de elementos en el arreglo y la cantidad de consultas, respectivamente.La segunda línea contiene
n enteros separados por espacio (), que representan los elementos iniciales del arreglo.Las siguientes
q líneas describen cada consulta:- Para las consultas de suma de rangos: la línea inicia con el número
1, seguido de dos enteros y (), que indican el intervalo de índices[ $$l_i, r_i$$ ]para el cual se desea calcular la suma.
- Para las consultas de actualización de arreglo: la línea inicia con el número
2, seguido de dos enteros y (), que indican el índice del elemento a actualizar y el nuevo valor .
Salida
Para cada consulta de suma de rangos, imprime en líneas separadas la suma de los valores dentro del intervalo especificado.
Ejemplos
Entrada | Salida |
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