重学Segment Tree

简介

貌似我用了两年的线段树一直是假的?!刚好这次有一道线段树合并的题,顺便重学一次Segment Tree

线段树的基本性质和操作

线段树采用二分的思想,用于区间查询,区间(单点)修改等操作
线段树T(a, b)可递归定义为

1
2
3
4
5
a != b
T[a, (a + b) >> 1]为T的左儿子
T[((a + b) >> 1) + 1, b]为T的有儿子
a == b
T为叶子结点

线段树结构体定义

1
2
3
struct segment_tree {
int l, r, w;
}tree[4 * Maxn + 1];

建树

  • 对于二分到的每一个节点,给它的左右端点确定范围
  • 如果是叶子节点,存储要维护的信息
  • 状态合并
1
2
3
4
5
6
7
8
9
10
void build(int l, int r, int cnt) {
tree[cnt].l = l, tree[cnt].r = r;
if (l == r) {
scanf("%d", &tree[cnt].w);
return ;
}
build(l, (l + r) >> 1, cnt * 2);
build(((l + r) >> 1) + 1, r, cnt * 2 + 1);
tree[cnt].w = tree[cnt * 2].w + tree[cnt * 2 + 1].w;
}

单点查询

  • 如果当前枚举的点为叶子节点,则为目标节点,负责进行二分
1
2
3
4
5
6
7
int ask(int cnt, int Aim) {
if (tree[cnt].l == tree[cnt].r)
return tree[cnt].w;
int mid = (tree[cnt].l + tree[cnt].r) >> 1;
if (Aim <= mid) return ask(cnt * 2, Aim);
else ask(cnt *2 + 1, Aim);
}

单点修改

  • 找到x的位置,根据建树状态合并的原理,修改每个节点的状态
1
2
3
4
5
6
7
8
9
10
void add(int cnt, int val, int Aim) {
if (tree[cnt].l == tree[cnt].r) {
tree[cnt].w += val;
return ;
}
int mid = (tree[cnt].l + tree[cnt].r) >> 1;
if (Aim <= mid) add(cnt * 2, val, Aim);
else add(cnt * 2 + 1, val, Aim);
tree[cnt].w = tree[cnt * 2].w + tree[cnt * 2 + 1].w;
}

区间查询

  • 当前节点区间的值是答案的一部分,则直接加上当前节点区间的状态
  • 当前节点区间只有一部分答案,暂时不加当前节点的状态,根据区间端点和中点的关系,继续递归左孩子或右孩子,直到满足情况1
  • 当前节点区间对答案没有任何贡献(实际上实现的时候是不存在这种情况的)
1
2
3
4
5
6
7
8
9
void query(int cnt, int l, int r) {
if (tree[cnt].l >= l && tree[cnt].r <= r) {
ans += tree[cnt].w;
return ;
}
int mid = (tree[cnt].l + tree[cnt].r) >> 1;
if (x <= mid) query(cnt * 2, l, r);
if (y < mid) query(cnt * 2 + 1, l, r);
}

区间修改

  • 懒标记
  • 直观理解:懒标记,用到才能动
  • 作用:存储这个节点的修改信息,暂时不把修改信息传到子节点。
  • 实现思路(重点):
    原结构体中增加新的变量,存储这个懒标记
    递归到这个节点时,只更新这个节点的状态,并把当前的更改值累积到标记中。
    当需要递归这个节点的子节点时,标记下传给子节点,两个都要传
    下传操作:
    ① 当前节点的懒标记累积到子节点的懒标记中
    ② 修改子节点状态,即原状态+子节点区间点的个数*父节点传下来的懒标记
    ③ 父节点懒标记清0
1
2
3
4
5
6
7
void down(int cnt) {
tree[cnt * 2].f += tree[cnt].f;
tree[cnt * 2 + 1].f += tree[cnt].f;
tree[cnt * 2].w += tree[cnt].f * (tree[cnt * 2].r - tree[cnt * 2].l + 1);
tree[cnt * 2 + 1].w += tree[cnt].f * (tree[cnt * 2 + 1].r - tree[cnt * 2 + 1].l + 1);
tree[cnt].f = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
void add(int cnt, int l, int r, int x, int val) {
if (tree[cnt].l >= l && tree[cnt].r <= r) {
tree[cnt].w += (tree[cnt].r - tree[cnt].l + 1) * val;
tree[cnt].f += x;
return 0;
}
if (tree[cnt].f) down(cnt);
int mid = (tree[cnt].l + tree[cnt].r) . 2;
if (l <= mid) add(cnt * 2);
if (r > mid) add(cnt * 2 + 1);
tree[cnt].w = tree[cnt * 2].w + tree[cnt * 2 + 1].w;
}
  • 懒标记对其他基本操作的影响
    在使用了懒标记的程序中,单点查询,区间查询,都要像区间修改那样对用得到的懒标记下传,就是加上一句if (tree[cnt].f) down(cnt);
  • 带懒标记的单点查询代码:
1
2
3
4
5
6
7
8
int ask(int cnt, int Aim) {
if (tree[cnt].l == tree[cnt].r)
return tree[cnt].w;
if (tree[cnt].f) down(cnt);
int mid = (tree[cnt].l + tree[cnt].r) >> 1;
if (Aim <= mid) return ask(cnt * 2, Aim);
else ask(cnt *2 + 1, Aim);
}
  • 带懒标记的区间查询代码:
1
2
3
4
5
6
7
8
9
10
void query(int cnt, int l, int r) {
if (tree[cnt].l >= l && tree[cnt].r <= r) {
ans += tree[cnt].w;
return ;
}
if (tree[cnt].f) down(cnt);
int mid = (tree[cnt].l + tree[cnt].r) >> 1;
if (x <= mid) query(cnt * 2, l, r);
if (y < mid) query(cnt * 2 + 1, l, r);
}

线段树的合并与分裂

线段树合并

1
2
3
4
merge(a, b):
如果左子树是空的,直接copy
如果右子树是空的,直接copy
如果左右子树都不是空的,Merge(tree[x1].lc, tree[x2].lc), Merge(tree[x1].rc, tree[x2].rc)
  • 在使用线段树合并解决一系列的合并问题的时候。要使用链式线段树存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int root[MaxN], tot;
struct Segment_Tree {
int l, r;
int lc, rc;
Info x;
Segment_Tree(int _l = 0, int _r = 0) {
l = _l, r = _r;
lc = rc = 0;
x = Info();
}
}tr[S];
int Merge(int x1, int x2) {
if (!x1) return x2;
if (!x2) return x1;
int now = Segment_Tree(tr[x1].l, tr[x1].r);
tr[now].lc = Merge(tr[x1].lc, tr[x2].lc);
tr[now].rc = Merge(tr[x1].rc, tr[x2].rc);
tr[now].x = tr[tr[now].lc].x + tr[tr[now].rc].x;
return now;
}

参考博客: Sdchr’s BlogTRTTG’s Blog

文章目录
  1. 1. 简介
  2. 2. 线段树的基本性质和操作
    1. 2.1. 线段树结构体定义
    2. 2.2. 建树
    3. 2.3. 单点查询
    4. 2.4. 单点修改
    5. 2.5. 区间查询
    6. 2.6. 区间修改
  3. 3. 线段树的合并与分裂
    1. 3.1. 线段树合并
,