Fenwick Tree Operations

You are given an array consisting of n integers and m operations. There are two types of operations:

• Update: Update the value at a given index.
• Query: Compute the sum of the values in a given subarray.

To solve this problem efficiently, you are required to use a Fenwick Tree (also known as a Binary Indexed Tree). A Fenwick Tree is a data structure that allows both updating an element and computing prefix sums in \(O(\log n)\) time. The key formula used to compute the sum in a range \([l, r]\) is:

[ \text{Sum}_{[l,r]} = \text{prefix}(r) - \text{prefix}(l-1), ]

where \(\text{prefix}(i)\) denotes the sum of the first \(i\) elements.

Note: All input should be read from standard input (stdin) and all output should be written to standard output (stdout).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of elements in the array and the number of operations respectively.

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

The following \(m\) lines each describe an operation in the format:

• For an update operation: 1 x y (update the element at position x to value y).
• For a query operation: 2 l r (query the sum of the segment from index l to r inclusive).

outputFormat

For each query operation (type 2), output the sum of the specified subarray on a separate line.

## sample

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

15
9
12
18

</p>