Segment Tree Range Sum and Update

You are given an array of integers. Your task is to perform a series of operations on the array. There are two types of operations:

• Update Operation: Given in the form 1 x y, update the value at position \( x \) (1-indexed) to \( y \).
• Range Sum Query: Given in the form 2 l r, compute the sum of the array from index \( l \) to \( r \) (both inclusive). The answer for each query should be printed on a new line.

To solve this problem efficiently, you are recommended to use a Segment Tree data structure. The segment tree is built in \( O(n) \) time and each query/update operation takes \( O(\log n) \) time, where \( n \) is the length of the array. The mathematical representation for the sum over an interval \( [l, r] \) is given by:

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

Read the input from standard input and write the output to standard output.

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 operations.

The second line contains \( n \) space-separated integers representing the initial values of the array.

The following \( q \) lines each represent an operation in one of the following formats:

• 1 x y : Update the element at position \( x \) (1-indexed) to \( y \).
• 2 l r : Print the sum of elements in the range from \( l \) to \( r \) (both inclusive).

outputFormat

For each query of type 2, output a single integer - the sum of the specified range on a new line.

## sample

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

15
13
10

</p>