P3368 【Template】Fenwick Tree 2

As stated, given a sequence, you need to perform the following two operations: 1. Add $x$ to every number in a given interval. 2. Query the value of a specific element.

The first line contains two integers $N$ and $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 $2$ or $4$ integers describing an operation, as follows: Operation 1: Format: `1 x y k` Meaning: add $k$ to every number in the interval $[x,y]$. Operation 2: Format: `2 x` Meaning: output the value of the $x$-th number.

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

Explanation for Sample 1:  Therefore, the outputs are $6$ and $10$. --- Constraints For $30\%$ of the testdata: $N\le8$, $M\le10$. For $70\%$ of the testdata: $N\le 10^4$, $M\le10^4$. For $100\%$ of the testdata: $1 \leq N, M\le 5\times10^5$, $1 \leq x, y \leq n$. It is guaranteed that at any time, the absolute value of any element in the sequence does not exceed $2^{30}$. Translated by ChatGPT 5