Sum Segtree

Description

Luogu P3372

As stated, you are given a sequence $a_i$ and need to perform two types of operations:

1. Add $k$ to every number in a given interval $[x,y]$.
2. Query the sum of all numbers in a given interval $[x,y]$.

Input Format

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$ integers $a_i$, where the i-th integer represents the initial value of the i-th element.

Each of the next $m$ lines contains either $3$ or $4$ integers, representing an operation in one of the following formats:

• 1 x y k: Add $k$ to every element in the range $[x, y]$.
• 2 x y: Output the sum of all elements in the range $[x, y]$.

Output Format

Output several lines of integers — the results of all type-2 operations, in the order they appear.

Samples

input #1:

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

output #1:

11
8
20

Constraints

$n,m \leq 10^5$

The sum of the sequence always $<2^{60}$.

Time Limit: 1.5s   |   Memory Limit: 256 MB

Practice Mode

💡 Tip: Press Ctrl + Enter (or ⌘ + Enter on Mac) to submit your code instantly.

C++ Python Submit