Genos Robot Team

Genos is in charge of managing his team of robots, each with a certain skill level. Under pressure from relentless adversaries, he must quickly update individual robot skill levels and answer queries regarding the cumulative capabilities of sub-teams. To achieve this efficiently, a Segment Tree data structure is employed, which allows both point updates and range sum queries in \(O(\log n)\) time.

There are two kinds of operations:

• 1 x v: Update the skill level of the x-th robot to v.
• 2 l r: Query the sum of skill levels from the l-th robot to the r-th robot (inclusive).

Note that the robots are numbered from 1 to \(n\). The input first specifies \(n\) (number of robots) and \(q\) (number of operations), followed by the initial skill levels and then \(q\) operations. Your task is to process all operations and output the answer for every range query.

The Segment Tree is built using an iterative approach where the tree is represented as an array of size \(2n\). Updates and queries are performed efficiently by propagating changes upward and aggregating sums from the relevant segments.

inputFormat

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

The first line contains two integers (n) and (q) representing the number of robots and the number of operations, respectively. The second line contains (n) space-separated integers representing the initial skill levels of the robots. Each of the following (q) lines represents an operation in one of the following two formats:

1. 1 x v: Update the skill level of the robot numbered (x) to (v).
2. 2 l r: Query the sum of skill levels for robots from index (l) to (r) (both inclusive).

Note: The indices are 1-based.

outputFormat

For each query operation (of the form 2 l r), output a single line containing the sum of the skill levels of the specified robots. If there are no query operations, output an empty string.## sample

5 4
1 2 3 4 5
2 1 3
1 2 6
2 1 3
2 2 5

6
10
18