Range Sum and Update Queries

You are given an array of integers and a list of queries. There are two types of queries:

• update i x: Update the element at index i to value x.
• sum l r: Compute the sum of the subarray from index l to r (inclusive).

You are required to process the queries efficiently. A common solution is to use a Fenwick Tree (or Binary Indexed Tree). The update and prefix sum operations of the Fenwick Tree can be represented by the following formulas in \( \text{\LaTeX} \):

Update: \( i \gets i + (i \& -i) \)

Prefix Sum: \( sum = \sum_{j=i}^{1} tree[j] \)

The queries must be processed in order, and only the sum queries produce an output.

inputFormat

The first line contains two integers n and q which represent the number of elements in the array and the number of queries, respectively.

The second line contains n integers representing the array elements.

Each of the next q lines contains a query in one of the following formats:

• update i x — update the element at index i to x.
• sum l r — output the sum of elements from index l to r (inclusive).

Input is read from stdin.

outputFormat

For each sum query, output the computed sum on a new line. No output is produced for update queries.

Output is written to stdout.

## sample

5 3
1 2 3 4 5
sum 1 3
update 2 10
sum 1 3

9
16

</p>