ADA University - January 13 - Segment Tree
Dima and array
Mother gave Dima as a present an array of length n. The array is not simple, but special. Dima can choose two numbers i and d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), and the element with index i magically becomes equal to d. Dima plays with his array, and mother gives his questions time from time - what is the sum of all the numbers in array with indexes from f to t inclusive? Dima easily managed this problem, but what about you?
The first line contains two integers n and q (1 ≤ n ≤ 5 *
105, 1 ≤ q ≤
105) - the number of elements in array and the total number of operations. In the next line n numbers are given:
an (-1000 ≤
ai ≤ 1000) - the initial state of array. The next q lines contain the operations and queries. The first character in the line can be either = or ?. If the line starts with =, this is an assignment operation. Next values are i and d, their restrictions are given earlier. If the line starts with ?, this is a query. Then go numbers f and t (1 ≤ f, t ≤ n).
For each query print on a separate line the sum of the numbers in array with indexes from f to t inclusive.
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3