【数据结构】线段树

引言

线段树虽然写起来没有树状数组那么简洁，时间效率也没有树状数组那么好，但是他的功能更加强大。

线段树

主要功能：

  • 单点更新、区间更新（lazy）
  • 单点查询、区间查询

剩下的不想多说了，太容易理解了，找个图一看就明白了～

只有一点要注意的：

  • 区间边界有没有包含在两棵相邻的子树内

线段树根据不同的题目变化很丰富，所以没有模板，只有大致的框架。

看应用中的例子吧～

应用

POJ 2828，建议自己思考一下这个题，挺有意思的一个小题～

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

using namespace std;

#define N 200010

int n;
int sum[N * 4];
int val[N], pos[N];
int ans[N];

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

void build(int u, int l, int r) {
    if (l == r) {
        sum[u] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pack(u);
}

int query(int u, int L, int R, int x) {
    if (L == R) return L;
    int MID = (L + R) >> 1;
    if (sum[u << 1] < x) return query(u << 1 | 1, MID + 1, R, x - sum[u << 1]);
    else return query(u << 1, L, MID, x);
}

void update(int u, int L, int R, int x) {
    // 此处的update可以和query写在一起，但是为了保留线段树的结构，此处保留update函数
    if (L == R) {
        sum[u] = 0;
        return;
    }
    int MID = (L + R) >> 1;
    if (MID < x) update(u << 1 | 1, MID + 1, R, x);
    else update(u << 1, L, MID, x);
    pack(u);
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &pos[i], &val[i]);
        }
        build(1, 1, n);
        for (int i = n - 1, res; i >= 0; i--) {
            res = query(1, 1, n, pos[i] + 1);
            ans[res] = val[i];
            update(1, 1, n, res);
        }
        for (int i = 1; i < n; i++) printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;
}

（待更新…）