【数据结构】线段树合集

更新于 分类于 ， 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 5 分钟

线段树是很实用的数据结构，除普通线段树外，有动态开点线段树、权值线段树、可持久化线段树，以及适用于多种题型，可以是其他算法的优化方法，十分灵活。

普通线段树

  • 维护区间的特殊信息
  • 本质：将区间不断分成左右两部分，每个区间是一个节点，利用二叉树结构维护区间信息，所以父节点u 的子节点编号是2u 和2u+1 ，区间[L,R] 的左右区间是[L,mid] 和(mid,R]
  • 建树：递归建左右区间
  • 维护/查询操作：当前区间为[L,R] ，须更新区间为[l,r] ，先求出L,R 的中间值mid ，有三种情况：
    • 若维护/查询区间是左区间[L,mid] 的子区间，就以[l,r] 递归维护/查询左区间
    • 若维护/查询区间是右区间(mid,R] 的子区间，就以[l,r] 递归维护/查询右区间
    • 若维护/查询区间横跨mid ，则分别以[l,mid],(mid,r] 递归维护/查询左右区间
    • 维护操作在上述操作结束后，进行pushup 操作，即用子区间更新后的信息来维护当前区间的信息
  • 4倍空间

lazy标记

  • 更新具有连续性，例如，先+1，再+2，可以在需要时直接+3，而不用分两步。
  • 对于系列更新操作，若不查询/若不更新到子节点，即不需要使用更新后的值，那就没有必要更新，也不需要告诉子节点“需要更新”。
  • 因此我们把需要更新的内容记录在区间对应的节点lazy上，等到需要的时候再将更新内容传递给子节点。
  • 传递过程是向下的，因此我写做pushdown。
  • 即，维护和查询时，先边界，再pushdown，再递归，（更新操作就再pushup）

带lazy标记的普通线段树代码（节点信息以数组存储，没有写成结构体）：

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
int L[N << 2], R[N << 2];
ll sum[N << 2], lazy[N << 2];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
inline void push_up(int rt) { sum[rt] = (sum[ls(rt)] + sum[rs(rt)]) % mod; }
inline void push_down(int rt)
{
    if (!lazy[rt])
        return;
    lazy[ls(rt)] += lazy[rt], lazy[rs(rt)] += lazy[rt];
    sum[ls(rt)] += lazy[rt] * (R[ls(rt)] - L[ls(rt)] + 1);
    sum[rs(rt)] += lazy[rt] * (R[rs(rt)] - L[rs(rt)] + 1);
    lazy[rt] = 0;
}
void build(int rt, int l, int r)
{
    L[rt] = l, R[rt] = r;
    if (l == r)
    {
        scanf("%lld", &sum[rt]);
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    push_up(rt);
}
void update(int rt, int l, int r, ll val)
{
    if (L[rt] == l && R[rt] == r)
    {
        lazy[rt] += val;
        sum[rt] += val * (r - l + 1);
        return;
    }
    push_down(rt);
    int mid = (L[rt] + R[rt]) >> 1;
    if (r <= mid)
        update(ls(rt), l, r, val);
    else if (l > mid)
        update(rs(rt), l, r, val);
    else
        update(ls(rt), l, mid, val), update(rs(rt), mid + 1, r, val);
    push_up(rt);
}
ll query(int rt, int l, int r)
{
    if (L[rt] == l && R[rt] == r)
        return sum[rt];
    push_down(rt);
    int mid = (L[rt] + R[rt]) >> 1;
    if (r <= mid)
        return query(ls(rt), l, r);
    if (l > mid)
        return query(rs(rt), l, r);
    return query(ls(rt), l, mid) + query(rs(rt), mid + 1, r);
}
  • 乘法和加法同时维护pushdown的修改：
    • 两个懒标记
    • sum[ls(rt)]=sum[ls(rt)]∗lazym[rt]+(R[ls(rt)]−L[ls(rt)]+1)∗lazya[rt]sum[ls(rt)]=sum[ls(rt)]*lazym[rt]+(R[ls(rt)]-L[ls(rt)]+1)*lazya[rt]
    • 孩子乘法标记*=父亲乘法标记
    • 孩子加法标记=孩子加法标记*父亲乘法标记+父亲加法标记
    • 父亲加法标记=0，乘法标记=1

离散化

对于所有的修改操作，离线处理，将涉及的区间映射到小范围的连续的数，对小范围建线段树处理

动态开点线段树

  • 不在一开始就把树建好，而是每更新/询问到一个不存在的区间时开新节点记录这个区间的信息
  • 动态开点时要单独记录每个节点的左右孩子信息，不能直接用二叉树的性质，因为并不是每个区间都有子节点（不一定是二叉树）
  • 由上述内容可知，动态开点线段树没有单独的建树过程，而是在修改过程中按需建树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// cnt是动态开点的节点下标
// ls/rs是储存左右节点下标的数组
// 初始调用时，int rt=0; update(rt,...);
inline void pushup(int rt) { a[rt] = a[ls[rt]] + a[rs[rt]]; }
void update(int& rt, int l, int r, int pos, int val) // 在pos位置插入元素val，注意是&rt
{
    if (!rt)
        rt = ++cnt;
    if (l == r)
    {
        a[rt] += val;
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
        update(ls[rt], l, mid, pos, val);
    else
        update(rs[rt], mid + 1, r, pos, val);
    pushup(rt);
}
  • 查询
1
2
3
4
5
6
7
8
9
10
11
12
13
int query(int rt, int l, int r, int x, int y)
{
    if (!rt || x > y)
        return 0;
    if(l==x&&r==y)
        return a[rt];
    int mid = l + r >> 1;
    if(y<=mid)
        return query(ls[rt], l, mid, x, y);
    if(x>mid)
        return query(rs[rt], mid + 1, r, x, y);
    return query(ls[rt], l, mid, x, mid) + query(rs[rt], mid + 1, r, mid + 1, y);
}

权值线段树

  • 权值线段树：维护区间内各元素出现次数
  • 作用
    • 数列第k大/小
    • 某个数的数列中排名
    • 比某个数大的最小值/比某个数小的最大值
  • 维护信息：叶子节点（元素出现次数），其他节点（子节点元素总数）
  • 注意：本节的线段树实现没有记录L[rt] 和R[rt] 。
  • 更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pushup(int rt) { a[rt] = a[ls(rt)] + a[rs(rt)]; }
void update(int rt, int l, int r, int k, int cnt) // 值为k的数多了cnt个
{
    if (l == r)
    {
        a[rt] += cnt; // 动态开点：先前没有这个节点
        return;
    }
    int mid = l + r >> 1;
    if (k <= mid)
        update(ls(rt), l, mid, k, cnt);
    else
        update(rs(rt), mid + 1, r, k, cnt);
    pushup(rt);
}
  • 查询元素val的个数：
1
2
3
4
5
6
7
8
9
int query(int rt, int l, int r, int val)
{
    if(l==r)
        return a[rt];
    int mid = l + r >> 1;
    if(val<=mid)
        return query(ls(rt), l, mid, val);
    return query(rs(rt), mid + 1, r, val);
}
  • 查询第k大：注意mid的值，左边比右边多1，因此是k-mid
1
2
3
4
5
6
7
8
9
int query(int rt, int l, int r, int k) // 查询第k大的数
{
    if (l == r)
        return l;
    int mid = l + r >> 1;
    if (k < mid)
        return query(rs(rt), mid + 1, r, k); // 右半部找第k大
    return query(ls(rt), l, mid, k - mid); // 右边比k个数多，在左边继续找
}
  • 查询区间[x,y] 有多少个数
1
2
3
4
5
6
7
8
9
10
11
int query(int rt, int l, int r, int x, int y)
{
    if (l == x && r == y)
        return a[rt];
    int mid = l + r >> 1;
    if (y <= mid)
        return query(ls(rt), l, mid, x, y);
    if (x > mid)
        return query(rs(rt), mid + 1, r, x, y);
    return query(ls(rt), l, mid, x, mid) + query(rs(rt), mid + 1, r, mid + 1, y);
}

可持久化线段树

zkw线段树

核心：自底向上

考虑一颗满二叉树作为线段树，可以发现叶子节点的规律：

叶子节点pp 的节点编号是p+8p+8 。

一般地，设需要维护的区间为[1,n][1,n] ，由于查询的需要（后面会说），需要扩展线段树维护的区间到[0,n+1][0,n+1]，则补齐满二叉树有h=⌈log⁡2(n+2)⌉h=\lceil\log_2 (n+2)\rceil 层（00 开始计数） ，叶子节点的序号为[0+2h,2h−1+2h][0+2^h,2^{h}-1+2^h] ，即叶子节点的起始序号为第一个≥n+2\geq n+2 的22 的幂次方mm 。对应区间序号[0+m,m−1+m][0+m,m-1+m]，我们想要的区间是[1+m,n+m][1+m,n+m] ，则有建树：

1
2
3
4
5
6
7
8
9
void build()
{
    // m = 1 << ceil(_lg(n + 2));
    for(m; m <= n + 1; m <<= 1);
    for(int i = 1; i <= n; i++)
        tree[i + m] = a[i];
    for(int i = m - 1; i; i--)
        tree[i] = tree[ls(i)] + tree[rs(i)];
}

单点修改：

1
2
3
4
5
void update(int pos, int val)
{
    for(int i = pos + m; i; i >>= 1)
        tree[i] += val;
}

查询区间和[l,r][l,r] ，首先扩充成(l−1,r+1)(l-1,r+1) ，根据下面算法手推一下更好理解。

1
2
3
4
5
6
7
8
9
10
int query(int l, int r)
{
    int ans = 0;
    for(l += m-1, r += m+1; l ^ r ^ 1; l >>= 1, r >>= 1)
    {
        if (~l & 1) ans += tree[l ^ 1]; // 左端点是左儿子
        if (r & 1) ans += tree[r ^ 1]; // 右端点是右儿子
    }
    return ans;
}