Dynamic Array Query Processing with Segment Tree

You are given an array of n integers and m queries. The queries are of two types:

• 1 i val: Update the i-th element of the array to val.
• 2 l r: Compute the sum of the subarray from index l to r (inclusive).

You need to process the queries in order and output the result for each sum query. The queries use 1-indexed positions.

This problem is typical in competitive programming and tests your ability to implement a segment tree to handle range queries efficiently.

The sum query result can be formally represented as follows:

\[ S(l, r) = \sum_{i=l}^{r} a_i \]

inputFormat

The first line contains two integers n and m, representing the number of elements in the array and the number of queries respectively.

The second line contains n space-separated integers denoting the elements of the array.

The next m lines each describe a query. A query is in one of the following two formats:

• 1 i val — update the element at index i to val.
• 2 l r — output the sum of the subarray from index l to r.

It is guaranteed that 1 ≤ i, l, r ≤ n.

outputFormat

For each query of type 2, output the sum of the queried subarray on a new line.

## sample

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

6
13
23

</p>