基础

概念

  线段树(Segment tree)是基于分治的二叉树，用于在区间上进行信息统计。线段树每个节点都代表一个区间，每个叶节点代表长度为1的区间，每个内部节点\([l,r]\)，左子节点\([l,mid]\)，右子节点\([mid+1,r]\)，其中\(mid=\lfloor\frac{l+r}{2}\rfloor\)。

  除去树的最后一层，整棵线段树一定是一颗完全二叉树，树的深度为\(O(\log{N})\)。我们将根节点编号为\(1\)，编号为\(x\)的节点左子节点为\(x*2\)，右子节点编号为\(x*2+1\)。\(N\)个叶节点的满二叉树有\(1+2+\cdots+\frac{N}{2}+N=2N-1\)个节点，而最后一层有空余，故保存线段树数组长度不小于\(4N\)。

  以区间最大值为例

  • 建树
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node {
    int l, r;
    int dat;
}t[N<<2];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    t[p].dat = max(t[p<<1].dat, t[p<<1|1].dat);
}
  • 单点修改

  从根节点出发，递归找到区间\([x,x]\)的节点，从下往上更新\([x,x]\)及所有父节点的信息，复杂度\(O(\log{N})\)。

1
2
3
4
5
6
7
void update(int p, int x, int v) {
    if (t[p].l == t[p].r) { t[p].dat = v; return; }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) update(p<<1, x, v);
    else update(p<<1 | 1, x, v);
    t[p].dat = max(t[p<<1].dat, t[p<<1|1].dat);
}
  • 区间查询
  1. 若\([l,r]\)完全覆盖当前节点区间，立即回溯，该节点\(dat\)为候选答案。
  2. 若左子节点与\([l,r]\)有重叠，递归访问左子节点。
  3. 若右子节点与\([l,r]\)有重叠，递归访问右子节点。
1
2
3
4
5
6
7
8
int query(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
    int mid = (t[p].l + t[p].r) >> 1;
    int ans = -INF;
    if (l <= mid) ans = max(ans, query(p<<1, l, r));
    if (r > mid) ans = max(ans, query(p<<1|1, l, r));
    return ans;
}
  • 延迟标记(lazy-tag)

  一般用于处理线段树的区间更新，如果某个节点被修改区间\([l,r]\)完全覆盖，以该节点为根的子树所有节点信息会发生变化，若逐一更新，一次区间修改时间复杂度为\(O(N)\)，为了提高效率，每次更新只更新到更新区间完全覆盖线段树节点区间为止，在被更新节点打上标记，下次访问节点再将标记传给子节点。

  什么时候用？统计量可合并、修改量可合并、通过修改量可直接修改统计量，即满⾜区间加法即可使用线段树维护信息。

P3372 线段树1

参考代码

P3373 线段树2

  本题有两种修改、一种查询取模后的结果共三种操作，向下传递lazy-tag时需考虑先后顺序，如果先加后乘则会有小数运算损失精度，所以先乘后加。

参考代码

经典应用

区间最值

bzoj1067 [SCOI2007]降雨量

题意：给出\(n(1\le n\le50000)\)条信息，第\(y_i(-10^9\le y_i\le10^9)\)年降雨量为\(r_i(-10^9\le r_i\le10^9)\)，给出\(m(1\le m\le10000)\)条询问，格式\(Y\)和\(X\)，\(X\)年是自\(Y\)年以来降雨量最多的。这句话是真、假或有可能。

  难点主要在分类讨论。

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
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 5e4 + 5, INF = 2e9;

struct Node {
    int l, r;
    int dat;
}t[N<<2];

int y[N], a[N], n, m;

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) { t[p].dat = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    t[p].dat = max(t[p<<1].dat, t[p<<1|1].dat);
}

int query(int p, int l, int r) {
    if (l > r) return -1;
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;
    int mid = (t[p].l + t[p].r) >> 1;
    int ans = -INF;
    if (l <= mid) ans = max(ans, query(p<<1, l, r));
    if (r > mid) ans = max(ans, query(p<<1|1, l, r));
    return ans;
}

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &y[i], &a[i]);
    }
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int p, q;
        scanf("%d%d", &p, &q);
        if (q < p) { puts("false"); continue; }
        int l = lower_bound(y + 1, y + n + 1, p) - y;
        int r = lower_bound(y + 1, y + n + 1, q) - y;
        if (y[l] == p && y[r] == q) {
            if (a[l] < a[r] || query(1, l + 1, r - 1) >= a[r]) puts("false");
            else if (q - p == r - l) puts("true");
            else puts("maybe");
        }
        else if (y[l] != p && y[r] != q) puts("maybe");
        else if (y[r] != q) {
            if (query(1, l + 1, r - 1) >= a[l]) puts("false");
            else puts("maybe");
        }
        else {
            if (query(1, l, r - 1) >= a[r]) puts("false");
            else puts("maybe");
        }
    }
    return 0;
}

区间求和

hdu4288 Coder

题意：有3种操作（1）add x:向序列添加x，添加后仍然有序；（2）del x:删除序列中值为x的元素；（3）sum:求下标模5为3的元素和。

  由于线段树不支持添加删除，采用离线做法。先离散化数组，用\(sum\)数组记录模5的5种情况和，从而添加或删除一个元素时对\(sum[1]\)修改，\(cnt\)表示线段树某节点区间数的个数，右子节点下标\(i\)在父节点对应下标\(i+lson.cnt\)，那么父节点\(sum[i]\)等于左子节点\(sum[i]\)加上右子节点\(sum[(i+lson.cnt)\%5]\)。

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
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 1e5 + 5, INF = 2e9;

struct Node {
    int l, r, cnt;
    ll sum[5];
}t[N<<2];

char q[N];
int a[N], b[N];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    t[p].cnt = 0;
    memset(t[p].sum, 0, sizeof(t[p].sum));
    if (l == r) { return; }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

void push_up(int p) {
    for (int i = 0; i < 5; ++i)
        t[p].sum[i] = t[p<<1].sum[i] + t[p<<1|1].sum[((i-t[p<<1].cnt)%5+5)%5];
}

void update(int p, int x, int y) {
    t[p].cnt += y;
    if (t[p].l == t[p].r) {
        t[p].sum[1] += y * b[x];
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) update(p<<1, x, y);
    else update(p<<1|1, x, y);
    push_up(p);
}

int main()
{
    int n;
    char op[5];
    while (~scanf("%d", &n)) {
        int num = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%s", op);
            q[i] = op[0];
            if (q[i] != 's') {
                scanf("%d", &a[i]);
                b[++num] = a[i];
            }
        }
        sort(b + 1, b + num + 1);
        num = unique(b + 1, b + num + 1) - b - 1;
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) {
            int pos = lower_bound(b + 1, b + num + 1, a[i]) - b;
            if (q[i] == 's') printf("%lld\n", t[1].sum[3]);
            else if (q[i] == 'a') update(1, pos, 1);
            else update(1, pos, -1);
        }
    }
    return 0;
}

poj3225 Help with Intervals

题意：给定初始集合为\(\varnothing\)，给出一系列（\(0\sim65535\)条）并(U)、交(I)、减(D)、被减(C)、异或(S)一个区间（区间\([0,65535]\)的子区间）命令，输出执行命令后的集合。

  建立线段树，区间包括的为1，不包括的为0。将区间扩大为两倍，线段数中偶数存点，奇数存线段，即0号表示\([0,0]\)，1号表示\((0,1)\)，2号表示\([1,1]\)，3号表示\((1,2)\cdots\)。那么

  U:区间\([l,r]\)置1

  I:区间\([-\infty,l)(r,\infty]\)置0

  D:区间\([l,r]\)置0

  C:区间\([-\infty,l)(r,\infty]\)置0，区间\([l,r]\)翻转\(0/1\)

  S:区间\([l,r]\)翻转\(0/1\)

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 65536 * 2, INF = 2e9;

struct Node {
    int l, r;
    int flip, dat;
}t[N<<2];

int id[N];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    t[p].flip = 0, t[p].dat = -1;
    if (l == r) { id[l] = p; return; }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
}

void push_down(int p) {
    if (t[p].dat != -1) {
        t[p<<1].dat = t[p<<1|1].dat = t[p].dat;
        t[p<<1].flip = t[p<<1|1].flip = 0;
        t[p].dat = -1;
    }
    if (t[p].flip) {
        t[p<<1].flip ^= 1;
        t[p<<1|1].flip ^= 1;
        t[p].flip = 0;
    }
}

void update(int p, int l, int r, int v) {
    if (l > r) return;
    if (l <= t[p].l && r >= t[p].r) {
        if (v != -1) {
            t[p].dat = v;
            t[p].flip = 0;
        }
        else t[p].flip ^= 1;
        return;
    }
    push_down(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) update(p<<1, l, r, v);
    if (r > mid) update(p<<1|1, l, r, v);
}

void query(int p) {
    if (t[p].l == t[p].r) {
        if (t[p].dat == -1) t[p].dat = 0;
        return;
    }
    push_down(p);
    query(p<<1);
    query(p<<1|1);
}

int main()
{
    char op, a, b;
    int l, r;
    build(1, 0, N);
    while (~scanf("%c %c%d,%d%c\n", &op, &a, &l, &r, &b)) {
        l = (l<<1) + (a == '(');
        r = (r<<1) - (b == ')');
        if (op == 'U') update(1, l, r, 1);
        else if (op == 'I') {
            update(1, 0, l - 1, 0);
            update(1, r + 1, N, 0);
        }
        else if (op == 'D') update(1, l, r, 0);
        else if (op == 'C') {
            update(1, 0, l - 1, 0);
            update(1, r + 1, N, 0);
            update(1, l, r, -1);
        }
        else update(1, l, r, -1);
    }
    query(1);
    int pre, flag = 0, ok = 0;
    for (int i = 0; i < N; ++i) {
        int p = id[i];
        int tmp = t[p].dat ^ t[p].flip;
        if (!tmp && flag) {
            if (ok) printf(" ");
            else ok = 1;
            if (pre & 1) printf("(");
            else printf("[");
            printf("%d,%d", pre / 2, i / 2);
            if (i % 2 == 0) printf(")");
            else printf("]");
            flag = 0;
        }
        else if (tmp && !flag) {
            pre = i;
            flag = 1;
        }
    }
    if (!ok) printf("empty set");
    puts("");
    return 0;
}