洛谷[P3372]线段树模板1

发表于 更新于 分类于

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 $k$。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
  2. 2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

1
2
3
11
8
20

提示

对于 $30%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <algorithm>
using namespace std;

#define LL long long
#define lr rt << 1
#define rr rt << 1 | 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 1e5 + 7;

int N, M, n, m;
LL add[maxn << 2], sum[maxn << 2];

namespace _lgl{

    inline void pushup(int rt){
        sum[rt] = sum[lr] + sum[rr];
    }

    inline void pushdown(int rt,int m){
        if(add[rt]) {
            add[lr] += add[rt];
            add[rr] += add[rt];
            sum[lr] += add[rt] * (m - (m >> 1));
            sum[rr] += add[rt] * (m >> 1); 
            add[rt] = 0;
        }
    }

    inline void build(int l,int r,int rt){
        if(l == r){
            scanf("%lld",&sum[rt]);
            return;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(rt);
    }

    inline void update(int L, int R, int c, int l, int r, int rt){
        if(L <= l && r <= R) {
            add[rt] += c;
            sum[rt] += (LL) c * (r - l + 1);
            return;
        }
        pushdown(rt, r - l + 1);
        int m = (l + r) >> 1;
        if(L <= m) update(L, R, c, lson);
        if(m < R) update(L, R, c, rson);
        pushup(rt);
    }

    inline LL query(int L, int R, int l, int r, int rt){
        if(L <= l && r <= R) return sum[rt];
        pushdown(rt, r - l + 1);
        LL ret = 0;
        int m = (l + r) >> 1;
        if(L <= m) ret += query(L, R, lson);
        if(m <  R) ret += query(L, R, rson);
        return ret;
    }

    inline void main(){
        scanf("%d%d",&N,&M);
        build(1, N, 1);
        while(M --){
            int a, b, c, skt;
            scanf("%d",&skt);
            if(skt == 2){
                scanf("%d%d",&a,&b);
                printf("%lld\n",query(a, b, 1, N, 1));
            }else{
                scanf("%d%d%d",&a,&b,&c);
                update(a, b, c, 1, N, 1);
            }
        }
        return;
    }

}

int main(){
    _lgl::main();
    return 0;
}