Query Processor on Array

You are given an integer array (A) of length (N), initially filled with zeros. Your task is to process (Q) queries on this array. There are two types of queries:

1. Update query: Given in the format 1 i x, set (A[i] = x).
2. Sum query: Given in the format 2 l r, compute the sum (\sum_{j=l}^{r} A[j]) and print it.

The problem requires that you process all queries in order and output the result of every sum query. Use (\texttt{stdin}) for input and (\texttt{stdout}) for output.

Constraints:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(0 \leq i < N\)
• \(0 \leq l \leq r < N\)
• \(0 \leq x \leq 10^9\)

Note: For efficient sum queries, consider using a Binary Indexed Tree (Fenwick Tree).

inputFormat

The first line contains two integers (N) and (Q), representing the size of the array and the number of queries respectively. Each of the next (Q) lines contains a query in one of the following formats:

• Update Query: 1 i x (set (A[i] = x))
• Sum Query: 2 l r (print the sum of the subarray from index (l) to (r) inclusive)

All input is read from standard input (stdin).

outputFormat

For each sum query, output the computed sum on a new line, in the order the queries are given. The output is printed to standard output (stdout).## sample

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

8
10