Taco: Range Sum Queries with Segment Tree

You are given an array \(A\) of \(N\) integers. Your task is to process \(M\) operations on the array. There are two types of operations:

• Update operation: Given an index \(x\) and a value \(y\), update the array such that \(A[x] = y\) (the index is 1-indexed).
• Range Sum Query: Given indices \(l\) and \(r\) (1-indexed), compute the sum \(\sum_{i=l}^{r} A[i]\).

To efficiently handle these operations, you are required to implement a Segment Tree data structure. The segment tree should support update and range sum query operations in \(O(\log N)\) time.

Note: The indices provided in the operations are 1-indexed while the underlying implementation may use 0-indexing.

inputFormat

The input is given via standard input (stdin) in the following format:

N
A[1] A[2] ... A[N]
M
op_1
op_2
...
op_M

Each op is given as three integers. If the first integer is 1, then the operation is an update operation and the next two integers are x and y (i.e. update A[x] to y). If the first integer is 2, then the operation is a range sum query and the next two integers are l and r (i.e. compute the sum from A[l] to A[r]).

outputFormat

For each range sum query (operation type 2), output the result on a separate line in standard output (stdout).

## sample

5
1 2 3 4 5
3
2 1 3
1 2 10
2 1 3

6
14

</p>