Array Query Processing using Segment Tree

You are given an array \(A = [a_1, a_2, \dots, a_N]\) of \(N\) integers and you need to process \(Q\) queries on it. The queries are of two types:

• Type 1 (Update Query): 1 K V. Update the \(K\)th element of the array to \(V\).
• Type 2 (Range Sum Query): 2 L R. Compute the sum \(\sum_{i=L}^{R} a_i\) (i.e. the sum from the \(L\)th to the \(R\)th element, inclusive).

Note that the array is 1-indexed. To efficiently process the queries, especially under tight constraints, you might want to use a segment tree data structure.

Example: Suppose \(A = [1, 2, 3, 4, 5]\) and the queries are as follows:

2 2 4
1 3 10
2 1 5

The first query asks for the sum from index 2 to 4, which is \(2 + 3 + 4 = 9\). Then the array is updated at index 3 to 10, resulting in \([1, 2, 10, 4, 5]\). Finally, the sum from index 1 to 5 is \(1 + 2 + 10 + 4 + 5 = 22\). The expected output is:

9
22

inputFormat

The first line contains two integers \(N\) and \(Q\), where \(N\) is the number of elements in the array and \(Q\) is the number of queries.

The second line contains \(N\) space-separated integers representing the initial array \(A\).

The next \(Q\) lines each contain a query in one of the following formats:

• 1 K V — Update the \(K\)th element of \(A\) to \(V\).
• 2 L R — Print the sum of elements from index \(L\) to \(R\) (inclusive).

All indices are 1-indexed.

outputFormat

For each query of the second type (range sum query), output the result on a separate line.

## sample

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

9
22

</p>