A Fenwick Tree Problem
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?
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.
On a new line, output an integer for every
Q2 query representing the answer to the respective queries.
5 2 3 1 0 5 2 Q1 1 3 Q2 2 4
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.