线段树简介

线段树是一种能把一些对于区间（或者线段）的修改、维护，从$O(n)$的时间复杂度优化为$O(logn)$的一种高级数据结构，线段树除了最后一层以外是满二叉树，可以使用堆来存，使用一个一维数组进行存储，一个简单存储[1,10]的一个线段树如下图所示：

pAgM5M8.jpg

线段树常见问题

线段树为什么开4倍区间大小的空间

将树看成是一个满二叉树来分析，假设有n个叶子节点，树的深度是k，那么$2^{k-1} \ge n$，则$k \ge 2^{log _2 n+1}$，最后一层节点数是$2^{\left \lfloor log _2 n \right \rfloor+1}$，根据满二叉树的性质，总节点数是$2n-1$，即$2^{\left \lfloor log _2 n \right \rfloor} \times 2 - 1$，即$4n$

线段树的时间复杂度为什么是$O(logn)$

假设待查找区间是$[L,R]$，当前节点的区间范围是$[T_L,T_R]$，需要分情况讨论：

  1. $T_L \le L \le T_R \le R$，这种情况下有分为两种，$mid = (T_L + T_R)/2$，一种$L < mid$只需要递归右边，另一种情况需要递归左右，但是如果这样的话不就不是$O(logn)$了吗？对这种情况进一步分析后，发现递归左边的区间是一定被查询区间所包含的，这样的话相当于多了长度是0的一条链
  2. $L \le T_L \le R \le T_R$，这种情况和1是对称的，不做讨论了
  3. $T_L \le L \le R \le T_R$，这种情况下分三种情况，$R \le mid$，只递归左边，$L > mid$，只递归右边，其他情况下，左右都要递归，但是这种情况下只会发生在根节点，也就是所最多发生一次

从上面的情况分析总的搜索次数是$4logn$，总时间复杂度是$O(logn)$

线段树常用操作

线段树的存储可以使用堆的存储方式，即使用一个一维数组从下标1开始存储，假设某个节点是$x$，$2x$表示该节点的左儿子节点，$2x+1$表示该节点的右儿子节点，$\left \lfloor x/2 \right \rfloor$ 表示该节点的父亲节点

pushup操作

pushup操作在根据题目中数据初始化线段树、修改操作的回溯修改父亲节点中使用，pushup只适用于对于线段树数据的单点修改操作，此处以求区间和为例，下面的模板代码不加说明都是求区间和的操作，下面是模板代码：

1
2
3
void pushup(int u) {  // 修改递归回溯时，对节点信息进行修改
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

build操作

build操作是建立线段树的操作，一般是依赖题目中给定的数据对线段树进行的初始化操作，build操作是一个递归建树操作，下面是具体模板代码：

1
2
3
4
5
6
7
8
9
void build(int u, int l, int r) {
    tr[u] = {l, r};
    if(l == r) {
        // 1.对线段树维护属性进行一定的计算后赋值或直接赋值，某些简单题目中不需要
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 2.递归建立左右子树
    pushup(u); // 3.如果不需要根据题目给定数据对线段树进行初始化，就不需要此行代码
}

query操作

query操作是查询线段树某个区间的属性的操作，一般是题目中要求的线段树所维护的属性，具体的代码因题目而定，下面是求区间和模板代码：

1
2
3
4
5
6
7
8
9
int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; // 此节点完全包括在查询区间内直接返回
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;  // v用于保存结果
    // 如果此节点区间没有完全被包含，且左子节点存在查询数据，则递归查找
    if(l <= mid) v = query(u << 1, l, r); 
    if(r > mid) v = v + query(u << 1 | 1, l, r); // 同理处理右子节点
    return v;
}

modify操作

modify操作是对线段树数据进行动态修改的操作，此操作比较简单不在赘述，以下是模板代码：

1
2
3
4
5
6
7
8
9
10
void modify(int u, int x, int v) { // u:修改节点 x:具体数据的下标 v:修改后的值
    // 表示已经到达叶子节点，直接修改sum值即可
    if(tr[u].l == x && tr[u].r == x) tr[u].sum = v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v); // 待修改节点在左子树上
        else modify(u << 1 | 1, x, v); // 待修改节点在右子树上
        pushup(u); // 重新计算一下此节点的维护的数据
    }
}

pushdown操作

pushdown操作是一个线段树的懒标记操作，使得线段树可以进行区间操作和区间查询，一般是在需要进行区间分裂的时候使用pushdown操作，在进行区间修改的最后使用pushup操作。

题目引入

吃个桃桃

Description

小陶玩了《黑神话 悟空》, 晚上做梦梦见自己在游戏内的世界遇到了一片神秘的森林, 森林里有N棵树, 每棵树上都有一些桃子, 并且还在不断的长出新的桃子.

天命人这时突然出现, 问小陶: “我要是随意划一片范围，你可能告诉我这一片当前总共有多少个桃子？”, 说罢随手摘了几个桃.

小陶即刻回道: “这有何难！”

Input

第一行输入为一个 int64 N, 表示接下来有 N 棵树, 之后 N 行每行一个 int64 整数 M, 第 i 行整数表示第 i 棵树当前的桃子数量. 第 N+2 行输入为一个 int64 J, 表示接下来有 J 个操作, 接下来 J 行每行三个 int64 整数 A B C, A 表示操作类型, B C 为对应操作的参数, A 共有三种可能输入：

  • 0: 询问当前 [B, C] 区间上的桃子总数.
  • 1: 第 B 棵树上长出了 C 个桃子.
  • 2: 天命人吃了 B 棵树上 C 个桃子.

Output

输出为每行一个 int64 数字, 输出询问总数的结果.

数据规模：1 <= N, J <= 10^5

Sample Input 1

1
2
3
4
5
6
7
8
9
10
11
12
5
1
2
3
4
5
5
0 0 4
1 0 1
0 0 1
2 0 1
0 0 4

Simple Output 1

1
2
3
15
4
15

AC代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
typedef unsigned long long ull;

using namespace std;

const int N = 1e5 + 10;
int n, m, a, b, c, nums[N];

struct Node {
    int l, r;
    long s;
} tr[N * 4];

void pushup(int u) {
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].s = nums[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

long query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
    int mid = (tr[u].l + tr[u].r) >> 1;
    long sum = 0;
    if (l <= mid) sum += query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

void modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].s += v;
    } else {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) modify1(u << 1, x, v);
        else modify1(u << 1 | 1, x, v);
        pushup(u);
    }
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
    }
    build(1, 1, n);
    cin >> m;
    while (m--) {
        cin >> a >> b >> c;
        if (a == 0) {
            cout << query(1, b + 1, c + 1) << endl;
        } else if (a == 1) {
            modify1(1, b + 1, c);
        } else if (a == 2) {
            modify2(1, b + 1, -c);
        }
    }
    
    return 0;
}

一个简单的整数问题

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 A[l],A[l+1],…,A[r]𝐴[𝑙],𝐴[𝑙+1],…,𝐴[𝑟] 都加上 d。
  2. Q l r，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 N，M。

第二行 𝑁 个整数 𝐴[𝑖]。

接下来 𝑀 行表示 𝑀 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

给定一个长度为 N𝑁 的数列 𝐴，以及 𝑀 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 A[l],A[l+1],…,A[r]𝐴[𝑙],𝐴[𝑙+1],…,𝐴[𝑟] 都加上 𝑑。
  2. Q l r，表示询问数列中第 𝑙∼𝑟 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 𝑁,𝑀。

第二行 𝑁 个整数 𝐴[𝑖]。

接下来 𝑀 行表示 𝑀 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1\le N,M \le10^5$
$|d|\le10000$
$|A[i]|\le10^9$

输入样例：

1
2
3
4
5
6
7
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

1
2
3
4
4
55
9
15

1≤N,M≤1051≤𝑁,𝑀≤105,
|d|≤10000|𝑑|≤10000,
|A[i]|≤109|𝐴[𝑖]|≤109

输入样例：

1
2
3
4
5
6
7
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

1
2
3
4
4
55
9
15

AC代码

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
typedef long long LL;

struct Node {
    int l, r;
    LL sum;
    int add;
}tr[N * 4];

int n, m, l, r, d;
int w[N];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.add) {
        left.sum += (LL)(left.r - left.l + 1) * root.add, left.add += root.add;
        right.sum += (LL)(right.r - right.l + 1) * root.add, right.add += root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r) {
    if(l == r) {
        tr[u] = {l, r};
        tr[u].sum = w[r];
        tr[u].add = 0;
    }
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(r > mid) modify(u << 1 | 1, l, r, d); // ****
        if(l <= mid) modify(u << 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL v = 0;
        if(l <= mid) v = query(u << 1, l, r);
        if(r > mid) v += query(u << 1 | 1, l, r); 
        pushup(u);
        return v;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    build(1, 1, n);
    char op[2];
    
    while(m --) {
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'C') {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }
    return 0;
}