P3374 [Template] Fenwick Tree 1

As stated, given a sequence, you need to perform the following two operations: - Add $x$ to a certain number. - Find the sum of all numbers in a given interval.

The first line contains two positive integers $n, m$, representing the number of elements in the sequence and the total number of operations. The second line contains $n$ space-separated integers, where the $i$-th number is the initial value of the $i$-th element of the sequence. Each of the next $m$ lines contains $3$ integers describing an operation, as follows: - `1 x k` Meaning: add $k$ to the $x$-th number. - `2 x y` Meaning: output the sum of all numbers in the interval $[x, y]$.

Output several lines of integers, which are the results of all type `2` operations.

Constraints For $30\%$ of the testdata, $1 \le n \le 8$, $1 \le m \le 10$. For $70\%$ of the testdata, $1 \le n, m \le 10^4$. For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$. It is guaranteed that at any time, the sum of any subarray of $a$ (including subarrays of length $1$ and length $n$) lies in the range $[-2^{31}, 2^{31})$. Sample explanation:  Therefore, the output is $14$ and $16$. Translated by ChatGPT 5