Fenwick Tree Operations

You are given a sequence of N positive integers and Q operations to perform on this sequence. There are two types of operations:

• 1 x y: Update the value at index x to y.
• 2 l r: Output the sum of all values in the subarray from index l to index r (inclusive).

You are required to implement these operations efficiently using a Fenwick Tree (also known as a Binary Indexed Tree (BIT)). In particular, if we define the tree array as \(T\), the update and query operations use the formulas:

Update: \( T[i] += \delta \) for appropriate indices \(i\) updated via \( i \mathrel{+}= (i \mathrel{\&} -i) \).

Query: The prefix sum from index 1 to \(i\) is computed as \( \sum_{j=1}^{i}{T[j]} \).

Process all operations, and for each query operation, print the answer on a new line.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains two integers N and Q separated by a space.

The second line contains N positive integers separated by spaces, representing the initial sequence.

Each of the next Q lines contains an operation in one of the following formats:

• 1 x y — Update the x-th element to y.

• 2 l r — Query and output the sum of the sequence from index l to r (inclusive).

outputFormat

For each query operation (operations of type 2), output a single integer on a new line representing the sum of the values in the specified range. If there are no query operations, print nothing.## sample

5 4
1 2 3 4 5
2 1 3
1 3 8
2 2 4
2 1 5

6
14
20