Module: Descomposición de la raíz


Problem

3 /6


Suma en segmento - 2

Theory Click to read/hide

Tenemos un problema sobre cómo calcular rápidamente las sumas en el segmento l...r en la matriz a, en la que los elementos pueden cambiar uno a la vez, en asintóticas menores que O(n).
Esta tarea se resuelve de manera similar a la anterior, pero al momento de solicitar un cambio, es necesario cambiar la cantidad en el bloque correspondiente.

Problem

Dada una matriz a de longitud n (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). También dado m (\(1 <= m <= 500\)) consultas como t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Si \(t = 0\), entonces la consulta debería mostrar la suma de números en el segmento desde l a r inclusive. Si \(t = 1\), entonces el número de elemento l se establece en r. Los elementos son numerados de 1 a n. 

 

Ejemplos

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!

# Entrada Salida
1
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
 3
7
5