Dynamic Array Range Sum Query

Problem Description

You are given an array of n integers. Your task is to perform q operations on this array. There are two types of operations:

• Update Operation: Update the element at a given index to a new value.
• Query Operation: Calculate the sum of elements in the range [l, r] (inclusive).

The operations are described in the input as follows. For an update operation, the input format is:
0 index value, which means updating A[index] to value.
For a query operation, the input format is:
1 l r, which means you must output the sum of the elements from index l to index r.

Using the prefix sum technique or a Binary Indexed Tree, you can perform both operations efficiently. In mathematical notation, the sum query for indices l to r is computed as:

$$S(l,r) = \sum_{i=l}^{r} A_i$$

Ensure that your solution processes the queries in order and outputs the result of each query operation on a new line.

inputFormat

Input Format

The first line of input contains two integers n and q separated by a space, 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 array.

The next q lines each contain an operation. Each operation is represented by three numbers:

• If the first number is 0, it indicates an update operation in the format: 0 index value.
• If the first number is 1, it indicates a query operation in the format: 1 l r.

All indices are 0-based.

outputFormat

Output Format

For each query operation (those starting with 1), output the sum of the specified range on a separate line.

## sample

3 3
1 3 5
1 0 2
0 1 2
1 0 2

9
8

</p>