Fenwick Tree Range Sum Query

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

• Update Query [1 x y]: Update the element at position x (1-indexed) to value y.
• Range Sum Query [2 l r]: Compute the sum of the elements with indices from l to r (inclusive, 1-indexed).

You are required to process all queries efficiently using a Fenwick Tree (also known as Binary Indexed Tree). The Fenwick Tree supports:

• An update operation in \(O(\log n)\) time.
• A prefix-sum (query) operation in \(O(\log n)\) time.

The Fenwick Tree data structure can be defined using the formula:

\[ index += index \& (-index) \quad \text{(for update)} \]

and for querying:

\[ index -= index \& (-index) \quad \text{(for query)} \]

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

inputFormat

The first line contains two integers n and q, representing 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 next q lines each contain a query in one of the following formats:

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

outputFormat

For each range sum query (queries of type 2), output the computed sum on a new line.

## sample

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

15
22
10
12

</p>