Sum of Numbers 7
Time limit2sMemory limit256 MB
Support point updates and range sum queries on an array of up to 1,000,000 elements over up to 1,000,000 operations, requiring a Fenwick tree or segment tree.
- Level
Medium4 of 10
- Topics
- Segment tree, Prefix sum, Array
- Solved
- No attempts yet
Problem
There is a sequence A of length N. Initially every element is 0.
Sum(i, j) returns the sum of all values between positions i and j, inclusive. If i is greater than j, it returns the sum from j through i. Modify(i, k) changes A[i] to k.
Given M commands in order, write a program that updates the sequence for each Modify command and prints the returned value for each Sum command.
Input
The first line contains N and M. (1 <= N <= 1,000,000, 1 <= M <= 1,000,000)
Each of the next M lines describes one command in execution order. If the first number is 0, the command is Sum and the next two numbers are i and j. If the first number is 1, the command is Modify and the next two numbers are i and k.
Initially A[i] = 0 for every i. For Modify commands, 1 <= k <= 100,000.
Output
For each Sum command, output its return value on its own line.