Segment Tree Queries

You are given an array of ( n ) integers. Your task is to process ( q ) commands which are either update or query operations. An update command is in the form U i x and updates the ( i)th element (1-indexed) of the array to ( x ). A query command is in the form Q l r and requires you to compute the sum of the array elements from index ( l ) to ( r ) (inclusive).

To perform these operations efficiently, you are expected to use a segment tree data structure. The segment tree is built on the array as follows: [ \text{tree}[i] = \text{tree}[2i] + \text{tree}[2i+1] ] for internal nodes. All indices in the commands are 1-indexed. Use the efficient update and query operations provided by the segment tree to solve the task.

inputFormat

The input is given via standard input. The first line contains an integer ( n ), the number of elements in the array. The second line contains ( n ) space-separated integers, the initial elements of the array. The third line contains an integer ( q ), the number of commands. Each of the following ( q ) lines contains a command in one of the following formats:

• Q l r — Query the sum from index \( l \) to \( r \) (inclusive).
• U i x — Update the \( i \)th element of the array to \( x \).

outputFormat

For each query command (Q l r), output the computed sum on a separate line via standard output.## sample

5
1 2 3 4 5
3
Q 1 3
U 2 10
Q 1 3

6
14