Segment Tree - Range Sum Query and Point Update

You are given an array of n integers and q queries. There are two types of queries:

• Update Query (Type 1): Change the value at a given position to a specified value.
• Sum Query (Type 2): Compute the sum of elements in a given range. The indices are 1-based.

Your task is to process these queries efficiently. A common approach is to use a segment tree data structure which allows both point updates and range sum queries in O(log n) time.

The sum query over a range \( [l, r] \) is computed as:

\( \text{sum} = \sum_{i=l}^{r} a_i \)

Implement the solution so that it reads from standard input and writes the output to standard output.

inputFormat

The first line of the input contains two integers n and q - the number of elements in the array and the number of queries respectively.

The second line contains n space-separated integers representing the initial array.

The following q lines each contain a query in one of the following formats:

• For an update query: 1 i x where i is the 1-based index whose value is to be changed to x.
• For a sum query: 2 l r where you need to output the sum of elements from index l to r (both inclusive).

outputFormat

For each query of type 2, output a single line containing the sum of the elements in the specified range.

## sample

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

6
16
3

</p>