简介 貌似我用了两年的线段树一直是假的?!刚好这次有一道线段树合并的题,顺便重学一次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 Blog TRTTG’s Blog