A Fenwick Tree Problem

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Bob is playing with an array!

Having studied the Fenwick Tree recently, Bob is curious whether he'd be able to solve the following types of operations to the array:

  • Q1 i j: Calculate and output the sum of the subarray between the indices \(i\) and \(j\) \((1 \le i \le j \le N)\) inclusive.
  • Q2 L R: Count and output the number of elements in the array with values in between \(L\) and \(R\) \((0 \le L \le R \le 10^5)\) inclusive.
  • U i v: Change the value of the \(i\)-th element \((1 \le i \le N)\) in the array to \(v\) \((0 \le v \le 10^5)\).

Unfortunately, Bob needs a little bit of help. Can you do it for him instead?

Input Specification

The first line contains two integers \(N\) and \(Q\) \((1 \le N, Q \le 10^5)\), the size of the array and the number of operations to the array.
The second line contains \(N\) nonnegative integers, each separated by a space. The value of these elements are nonnegative and will never exceed \(10^5\).
The next \(Q\) lines each contain an operation to be performed on the array.

The values inside the array will always be between \(0\) and \(10^5\) inclusive.

Output Specification

On a new line, output an integer for every Q1 and Q2 query representing the answer to the respective queries.

Sample Input

5 2
3 1 0 5 2
Q1 1 3
Q2 2 4

Sample Output


Explanation of Output

The sum of the subarray can be described as \(3 + 1 + 0 = 4\) (These are the first three elements in the array).

Overall, there are \(2\) elements that fall in the range \([2, 4]\), which are the first and last elements in the array.


There are no comments at the moment.