Range Sum Query with Updates

You are given an array of N integers and Q operations. There are two types of operations:

• Update Operation: 1 x y — update the element at index x (1-indexed) to y.
• Query Operation: 2 l r — output the sum of the subarray from index l to r (both ends inclusive).

A common approach to solve this problem is to use a Segment Tree. The segment tree is built based on the formula

for internal nodes, which allows both efficient updates and range sum queries.

Your task is to implement the segment tree operations to support both update and query operations from stdin and output the results to stdout.

inputFormat

The first line contains two integers N and Q representing the size of the array and the number of operations respectively.\nThe second line contains N space-separated integers representing the initial array.\nEach of the following Q lines contains an operation in one of the following formats:\n1. Update: 1 x y (update the element at index x to y, where indices are 1-indexed)\n2. Query: 2 l r (query the sum of the subarray from index l to r, both inclusive)

outputFormat

For each query operation, output the computed sum on a separate line to stdout.## sample

5 3
5 2 4 7 10
2 1 3
1 2 8
2 2 4

11
19