王皓宇
(小鸽子)
1
最惨的一次，老师都说了是主席树（甚至是赛中），都只能用二分写，仅仅只有非常绝望的15分（开long long就60了，对不起，我的锅，大家不要学我）
现在已经补完（能做的）题了，也是总结一下（断更了近半年，对不起，我的锅）
☆☆☆主席树（可持久化线段树）☆☆☆
Part 1 介绍（？
说到线段树可熟了，主席树也就是动态开点线段树Pro
比如这张图，改变4号叶子节点实则只会影响图中所有打X的点
那么为了记录线段树的历史版本，用主席树的时空消耗肯定是比单独建树更优的（如下图
其中对于重复的节点就不用白白浪费空间了，而查询时间是完全不逊色
Part 2 实现部分
重点是“建”新树
结构体设置
struct point
{
int l;//左儿子
int r;//右儿子
int ……//其他要维护的东西（因题而异？
}
首先我们要知道，因为要记录多个历史版本，如果用不同数组存放，会有空间冗余，因为你不得不记录初始树，定义了极大空间，而且往往用不到
所以我们动态开点，唯一不便的地方是左儿子不一定再是P*2，右也不一定是P*2+1
建立新节点
void insert(int &now,int pre,int l,int r,int p)//目前开点，历史节点，目前左端点、右端点，目标端点
{
t[now = ++cnt] = t[pre];//开点并继承数据
if(l==r)
{
/*
根据题目做相应的处理（不绝对
*/
return ;
}
int mid = (l+r)/2;
if(p<=mid)//更新目标所在的子树，另一个直接继承了
ist(t[now].l,t[pre].l,l,mid,p);
else
ist(t[now].r,t[pre].r,mid+1,r,p);
pushup(now);//更新
}
另外的完全照抄动态开点线段树就OK了
我靠，已经放学5分钟了
跑路了兄弟，跑路了
4 个赞
