线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 nlog⁡nn\log_{}{n} 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对 33 取模然后对 44 取模，两个操作就不能合并在一起做）。

ckUHD1.png

加法线段树

模板题：洛谷 P3372 | [模板] 线段树 1

题目描述

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

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

输入格式

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

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

接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：

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

输出格式

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

输入输出样例

输入 #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%30\% 的数据： n≤8，m≤10n \le 8，m \le 10 。
对于 70%70\% 的数据： n≤103，m≤104n \le {10}^3，m \le {10}^4 。
对于 100%100\% 的数据： 1≤n,m≤1051 \le n, m \le {10}^5 。

保证任意时刻数列中任意元素的和在 [−263,263)[-2^{63}, 2^{63}) 内。

解决方案

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
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100500;
int n, m;
long long a[maxn], tree[maxn << 2], lazy[maxn << 2];	//开四倍空间

void pushup(int rt)
{
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int rt, int ln, int rn)
{
    if (lazy[rt])	//下传lazy标签
    {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        tree[rt << 1] += ln * lazy[rt];
        tree[rt << 1 | 1] += rn * lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int l, int r, int rt)
{
    if (l == r)
    {
        tree[rt] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

void add(int L, int R, int l, int r, int rt, int k)
{
    if (L <= l && R >= r)
    {
        tree[rt] += (r - l + 1) * k;
        lazy[rt] += k;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid)
        add(L, R, l, mid, rt << 1, k);
    if (R > mid)
        add(L, R, mid + 1, r, rt << 1 | 1, k);
    pushup(rt);	//每次更新都记得pushup一下
}

long long query(int L, int R, int l, int r, int rt)
{
    if (L <= l && R >= r)
    {
        return tree[rt];
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    long long ans = 0;
    if (L <= mid)
        ans += query(L, R, l, mid, rt << 1);
    if (R > mid)
        ans += query(L, R, mid + 1, r, rt << 1 | 1);
    return ans;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    build(1, n, 1);
    for (int i = 1; i <= m; i++)
    {
        int op, x, y, k;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d %d %d", &x, &y, &k);
            add(x, y, 1, n, 1, k);
        }
        if (op == 2)
        {
            scanf("%d %d", &x, &y);
            printf("%lld\n", query(x, y, 1, n, 1));
        }
    }
    return 0;
}

乘法线段树

请参阅