Module: Root decomposition


Problem

3 /6


Sum on segment - 2

Theory Click to read/hide

We have a problem about how to quickly calculate the sums on the segment l...r in the array a, in which the elements can change one at a time, in asymptotics less than O(n).
This task is solved similarly to the previous one, but when requesting a change, you need to change the amount in the corresponding block.

Problem

Given an array a of length n (\(1 <= n <= 2 \cdot 10^6\)< /span>, \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

If \(t = 0\), then the query should display the sum of numbers in the segment from l to r inclusive. If \(t = 1\), then element number l is set to r. Elements are numbered from 1 to n. 

 

Examples
# Input Output
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!