526互联

关于线段树

发布时间 2023-10-05 19:59:41作者: Biuld

动态开点

当到了未建立过的新点时再建立点，一般用结构体来存储线段树。

大致代码：

#define lx tree[x].l
#define rx tree[x].r
#define mid ((l + r) >> 1)

int cnt;
struct node{
	int l, r;
	int v;
}tree[N << 5];

inline void pushup(int x){
	tree[x].v = tree[lx].v + tree[rx].v;
}

inline int update(int x, int l, int r, int k, int s){ //此处以单点修改展示
	if(!x) x = ++ cnt;
	
	if(l == r){
	tree[x].v = s;
		return x;
	}
	
	if(k <= mid) tree[x].l = update(lx, l, mid, k);
	if(mid < k) tree[x].r = update(rx, mid + 1, r, k);
	
	pushup(x);
	return x;
}

关于线段树开的空间……
我的评价是：能开大点就开大点，保险

可持久化

常在多颗线段树差异不大但都需访问时使用
即在动态开点上加个记录时间的标记（也可以是其他标记），以达到节省空间开多颗线段树
用 \(rt_i\) 表示第 \(i\) 颗线段树的根节点

注意点：

  1. 一定要先建 \(rt[0]\) 的初始树，即使它可能是颗空树
  2. 开新点的过程大多为直接复制原节点再修改
  3. 相比正常线段树需多用一 \(vis\) 数组来表示该点是否开过
  4. 一定要有回传标号的操作
  5. 可持久化不能使用线段树合并
int rt[N], cnt;
struct node{
	int l, r;
	int v;
	bool vis; //vis 表示当点是否被开过
}tree[N << 5];

inline void pushup(int x){
	tree[x].v = tree[lx].v + tree[rx].v;
}

inline int build(int x, int l, int r){
	x = ++ cnt;
	
	if(l == r){
		return x; //回传标号
	}
	
	tree[x].l = build(lx, l, mid);
	tree[x].r = build(rx, mid + 1, r);
	
	return x; //同上
}

inline int add(int x){
	tree[++ cnt] = tree[x];
	tree[cnt].vis = 1;
	tree[tree[cnt].l].vis = 0;
	tree[tree[cnt].r].vis = 0;
	return cnt;
}

inline int update(int x, int l, int r, int k, int s){
	if(!tree[x].vis){
		x = add(x);
	}
	
	if(l == r){
		tree[x].v = s;
		tree[x].vis = 1;
		return x;
	}
	
	if(k <= mid) tree[x].l = update(lx, l, mid, k, s);
	if(mid < k) tree[x].r = update(rx, mid + 1, r, k, s);
	
	pushup(x);
	return x;
}

int main(){
	rt[0] = build(1, 1, n);
	for(int i = 1; i <= n; ++ i){
		rt[i] = add(rt[i - 1]); //第 i 颗树继承（复制）第 i - 1 颗树
		rt[i] = update(rt[i], 1, n, i, 1);
	}
}