Consultas de Soma em Intervalos 2

Tens um array com n elementos e q consultas. Existem dois tipos de consultas:

1. Obter a soma num intervalo específico

2. 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:

1. Para consultas de soma em intervalo: a linha começa com o número 1 seguido de dois inteiros e (). Este intervalo [] indica os limites para os quais deves calcular a soma dos elementos.

2. Para consultas de atualização do array: a linha começa com o número 2 seguido 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