Efficient Array Operations with Updates and Range Queries

You are given an array of n integers. You need to process a sequence of q operations on this array. There are two types of operations:

• Update Operation: 1 i x — update the value at position i to x.
• Query Operation: 2 l r — compute the sum of the subarray from index l to r (inclusive).

The operations are given in the input via standard input, and for each query operation, you should output the resulting sum to standard output.

An efficient solution uses a Fenwick Tree (also known as a Binary Indexed Tree). The key update step in a Fenwick Tree is given by:

[ i \mathrel{+}= i , & , -i ]

which allows both update and prefix sum queries to be done in \(O(\log n)\) time.

inputFormat

The first line of input contains two integers n and q, denoting the size of the array and the number of operations, respectively. The second line contains n space-separated integers representing the initial array. Each of the following q lines contains an operation in one of the two formats:

• 1 i x: Update the number at index i to x.
• 2 l r: Query the sum of the subarray from index l to r.

Note: The indices are 1-indexed.

outputFormat

For each query operation (type 2), output the sum of the subarray from index l to r on a new line. If there are no query operations, the output is empty.

## sample

5 4
1 3 5 7 9
2 1 3
1 2 10
2 2 4
2 1 5

9
22
32

</p>