线段树进阶

线段树进阶

动态开点

定义

动态存储数据的线段树，可以优化空间复杂度

实现

为了避免 \(N<<1\) ，不再使用完全二叉树存储，而记录左右儿子 \(ls,rs\) 此外需要 \(tot\) 记录已经开了多少点

在递归时要记录点的左右区间，确保开点时能知道区间大小

void modify(int &p,int L,int R,int l,int r,int v){//big->pointlr small->modifylr
	if(!p)p = mknode();
	t[p].l = L,t[p].r = R;
	int siz=R-L+1;
	if(l<=L&&R<=r){
		t[p].sum += 1ll*siz(p)*v;
		t[p].add += v;
		return;
	}
	pushdown(p);
	int mid=L+R>>1;
	if(l<=mid)
		modify(t[p].ls,L,mid,l,r,v);
	if(r>mid)
		modify(t[p].rs,mid+1,R,l,r,v);
	pushup(p);
}

long long query(int p,int L,int R,int l,int r){
	if(!p)return 0;//没有该节点 返回0
	if(l<=L&&R<=r)return t[p].sum;
	int mid=L+R>>1;
	long long ans=0;
	pushdown(p);
	if(l<=mid)ans+=query(t[p].ls,L,mid,l,r);
	if(r>mid)ans+=query(t[p].rs,mid+1,R,l,r);
	return ans;
}

空间复杂度

\(O(min(m\log n,n*2))\)

不要像我一样 mknode 写错 tot 加了两次，搞得数据隔一点存一个然后 RE

还要注意 root 也会占线段树的空间为 O(n(\logn + 1))

线段树合并

需要用到动态开点。

不过就是遍历树然后刷新节点，然后pushup。时间复杂度要具体情况具体分析，比如雨天的尾巴，据分析。线段树合并过程中发生递归，p，q之一会被删除，所以merge函数被调用的次数不超过所有点数加一。 \(O((m+n)\log |V|)\)

int merge(int p,int q,int L,int R){
	if(!p)return q;
	if(!q)return p;
	if(L==R){
		t[p].dat += t[q].dat;
		t[p].pos = t[p].dat?L:0; 
		return p;
	}
	int mid=L+R>>1;
	t[p].ls = merge(t[p].ls,t[q].ls,L,mid);
	t[p].rs = merge(t[p].rs,t[q].rs,mid+1,R);
	pushup(p);
	return p;
}

优化建图

一个区间每个点对一个点进行连边。可以建立线段树，线段树内部边权根据问题而定。如果要分入边和出边，就建两棵树，入树和出树，注意两棵树的叶子节点是一样的，可以使用动态开点实现。

标记永久化

适当的时候，不下传标记，而是查询时一层层递归，累加答案，优化时间复杂度。

可持久化

参见主席树

练习题

学而不思则妄，思而不学则殆

【模板】线段树 1 提示：动态开点

【模板】线段树合并 提示：线段树合并，树上差分

【模板】线段树分裂

Legacy 提示：线段树优化建图

参考资料

线段树合并时间复杂度证明