Module: Decomposição de raiz


Problem

3 /6


Soma no segmento - 2

Theory Click to read/hide

Temos um problema sobre como calcular rapidamente as somas do segmento l...r no array a, no qual os elementos podem mudar um de cada vez, em assintóticas menores que O(n).
Esta tarefa é resolvida de forma semelhante à anterior, mas ao solicitar uma alteração, você precisa alterar o valor no bloco correspondente.

Problem

Dado um array a de comprimento n (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). Também fornece m (\(1 <= m <= 500\)) consultas como t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Se \(t = 0\), a consulta deve exibir a soma dos números no segmento de l para r inclusive. Se \(t = 1\), o número do elemento l é definido como r. Os elementos são numerado de 1 a n. 

 

Exemplos
# Entrada Saída
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!