线段树专题(动态开点线段树, 权值线段树, 线段树合并, 可持久化线段树)

发表于 更新于 阅读次数：
线段树, 动态开点线段树, 权值线段树, 线段树合并, 可持久化线段树

动态开点线段树

动态开点线段树应用于需要维护的数列长度过大, 正常线段树存不下的时候.
我们需要动态的开点, 因此不能用 rt<<1 和 rt<<1|1 来表示左右子节点, 而需要在 node 中记录 lson 和 rson 的编号, 如下.

1
2
3
4
5
struct node 
{
    int l, r, val, lazy;
}st[maxn];

update 时如果需要开点则开点. 

1
2
3
4
5
6
7
8
9
10
11
12

void update(int &rt, int l, int r, ...)
{
    if(!rt) rt = ++cnt;
    if(l == r)
        return ;
    if() update(...);
    if() update(...);
    return ;
    pushup(rt);
}

查询时同理.

1
2
3
4
5
6
7
8
9
10
11
12

int ask(int rt, int l, int r, int L, int R...)
{
    if(!rt) return 0; 
    if(l <= L && R <= r)
    {
        ...
    }
    ...
    return val;
}

权值线段树

什么是权值线段树?

以权值为维护信息的线段树，本质仍是线段树。、

不同于普通线段树维护的区间信息, 权值线段树维护的是固定值域内的元素的个数.
这不就是桶嘛

举个栗子
有个数列 $ 1, 1, 2, 2, 2, 3, 3, 4, 5 $
节点 $ [1, 1] $ 的值为 2 代表数列中位于 $ [1, 1] $ 的数有 2 个.
同理节点 $ [1, 2] $ 的值为 5 , $ [1, 5] $ 的值为 9 .

主席树（可持久化线段树）

主席树是一种霸气的，持久的，基于线段树的数据结构。

可持久化线段树, 顾名思义, 就是支持回退操作的线段树(完全理解不了好不好)

主席树由权值线段树引申而来, 可以维护区间第k小.
思想是开一个 root[] 数组存储 i 版本的根节点.
每次更新时对于需要更新的节点直接新建, 对于不需要更新的节点直接连到更新的节点上.

附上主席树求区间第k小代码

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
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define rep(i, a, b) for(int i=(a); i<=(b); i++)
#define ll long long
#define maxn 1000020
int a[maxn], b[maxn], t[maxn], n, m, k;
struct str
{
	int l, r, val;
}tree[maxn<<5];
int top;
inline int read()
{
	char ch=getchar(); int ans=0;
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^48), ch=getchar();
	return ans;
}
inline int build(int l, int r)
{
	int node=++top;
	if(l!=r)
	{
		tree[node].l=build(l, mid);
		tree[node].r=build(mid+1, r);
	}
	return node;
}
inline int clone(int node)
{
	tree[++top]=tree[node];
	tree[top].val++;
	return top;
}
inline int update(int pre, int l, int r, int x)
{
	int node=clone(pre);
	if(l!=r)
	{
		if(x<=mid)	tree[node].l=update(tree[node].l, l, mid, x);
		else		tree[node].r=update(tree[node].r, mid+1, r, x);
	}
	return node;
}
inline int query(int u, int v, int l, int r, int k)
{
	if(l==r)	return b[l];
	else
	{
		int node=tree[tree[v].l].val-tree[tree[u].l].val;
		if(k<=node)	return query(tree[u].l, tree[v].l, l, mid, k);
		else		return query(tree[u].r, tree[v].r, mid+1, r, k-node);
	}
}
signed main()
{
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]), b[i]=a[i];
	sort(b+1, b+n+1);
	int size=unique(b+1, b+n+1)-(b+1);
	rep(i, 1, n)
	{
		int x=lower_bound(b+1, b+size+1, a[i])-b;
		t[i]=update(t[i-1], 1, size, x);
	}
	rep(i, 1, m)
	{
		int l=read(), r=read(), k=read();
		printf("%d\n", query(t[l-1], t[r], 1, size, k));
	}
	return 0;
}

线段树合并

待更

例题

待更