Consultas de Soma em Intervalos 2
Tens um array com
n elementos e q consultas. Existem dois tipos de consultas:- Obter a soma num intervalo específico
- Atualizar o elemento do array numa dada posição
O teu objetivo é processar essas consultas de forma eficiente.
Entrada
A primeira linha da entrada contém dois inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam o número de elementos do array e o número de consultas, respetivamente.A segunda linha contém
n inteiros separados por espaços, (), que representam os valores iniciais do array.As
q linhas seguintes descrevem cada consulta:- Para consultas de soma em intervalo: a linha começa com o número
1seguido de dois inteiros e (). Este intervalo[]indica os limites para os quais deves calcular a soma dos elementos.
- Para consultas de atualização do array: a linha começa com o número
2seguido de dois inteiros e (). O índice indica a posição do elemento a atualizar e é o novo valor.
Saída
Para cada consulta de soma em intervalo, imprime a soma dos valores no intervalo especificado, cada resultado numa linha separada.
Exemplos
Entrada | Saída |
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