Segment Tree Practice 1

View as PDF

Submit solution

Points: 12
Time limit: 0.6s
Memory limit: 256M

Problem type

Given an array A of size N, support the Q of the following operations:

  1. Find the sum of all elements from index l to index r.
  2. Update the element at index i to value x.


1 \le N, Q \le 2 \times 10^5

1 \le l \le r \le N

1 \le i \le N

1 \le A_i, x \le 10^9

Input Specification

The first line contains 2 integers N and Q.

The second line contains N integers A_1, A_2, \ldots, A_N, the initial elements of A.

The next Q lines are one of two forms:

  1. S l r representing the first operation.
  2. U i x representing the second operation.

Output Specification

For each type 1 operation output one integer on its own line, the answer to that query.

Sample Input

5 5
1 2 3 4 5
S 2 4
S 1 5
U 2 6
S 2 2
S 2 4

Sample Output



There are no comments at the moment.