P3372 【Template】Segment Tree 1

As stated, given a sequence $\{a_i\}$, you need to perform the following two operations: 1. Add $k$ to every number in a given interval. 2. Find the sum of all numbers in a given interval.

The first line contains two 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 $a_i$, where the $i$-th integer is the initial value of the $i$-th element. Each of the next $m$ lines contains $3$ or $4$ integers representing an operation, as follows: 1. `1 x y k`: add $k$ to every number in the interval $[x, y]$. 2. `2 x y`: 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.

For 15% of the testdata: $n \le 8$, $m \le 10$. For 35% of the testdata: $n \le {10}^3$, $m \le {10}^4$. For 100% of the testdata: $1 \le n, m \le {10}^5$, $a_i, k$ are positive, and the sum of the sequence at any time does not exceed $2\times 10^{18}$. Sample Explanation.  Translated by ChatGPT 5