[总结]
由上面的分析介绍, 我们可以发现伸展树有以下几个优点:(1)时间复杂度低, 伸展树的各种基本操作的平摊复杂度都是 O(log n)的. 在树状数据结构中, 无疑是非常优秀的.
(2)空间要求不高. 与红黑树需要记录每个节点的颜色, AVL 树需要记录平衡因子不同, 伸展树不需要记录任何信息以保持树的平衡.(3)算法简单, 编程容易. 伸展树的基本操作都是以 Splay 操作为基础的, 而 Splay 操作中只需根据当前节点的位置进行旋转操作即可.
上题参考代码:
- /**************************************************************
- Problem: 1588
- User: SongHL
- Language: C++
- Result: Accepted
- Time:1284 ms
- Memory:2068 kb
- ****************************************************************/
- #include<bits/stdc++.h>
- const int INF=0x3f3f3f3f;
- using namespace std;
- int ans,n,t1,t2,rt,size;
- int tr[50001][2],fa[50001],num[50001];
- void rotate(int x,int &k)
- {
- int y=fa[x],z=fa[y],l,r;
- if(tr[y][0]==x)l=0;else l=1;r=l^1;
- if(y==k)k=x;
- else{if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;}
- fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
- tr[y][l]=tr[x][r];tr[x][r]=y;
- }
- void splay(int x,int &k)
- {
- int y,z;
- while(x!=k)
- {
- y=fa[x],z=fa[y];
- if(y!=k)
- {
- if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k);
- else rotate(y,k);
- }
- rotate(x,k);
- }
- }
- void ins(int &k,int x,int last)
- {
- if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}
- if(x<num[k])ins(tr[k][0],x,k);
- else ins(tr[k][1],x,k);
- }
- void ask_before(int k,int x)
- {
- if(k==0)return;
- if(num[k]<=x){t1=num[k];ask_before(tr[k][1],x);}
- else ask_before(tr[k][0],x);
- }
- void ask_after(int k,int x)
- {
- if(k==0)return;
- if(num[k]>=x){t2=num[k];ask_after(tr[k][0],x);}
- else ask_after(tr[k][1],x);
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- int x;if(scanf("%d",&x)==EOF) x=0;
- t1=-INF;t2=INF;
- ask_before(rt,x);
- ask_after(rt,x);
- if(i!=1)ans+=min(x-t1,t2-x);
- else ans+=x;
- ins(rt,x,0);
- }
- printf("%d",ans);
- return 0;
- }
- View Code
[NOI2005]维修数列(Splay 的其他操作)
https://www.lydsy.com/JudgeOnline/problem.php?id=1500
算法过程:
初始化
首先, 对于原序列, 我们不应该一个一个读入, 然后插入, 那么效率就是 O(nlogn), 而 splay 的常数本身就很大, 所以考虑一个优化, 就是把原序列一次性读入后, 直接类似线段树的 build, 搞一个整体建树, 即不断的将当前点维护的区间进行二分, 到达单元素区间后, 就把对应的序列值插入进去, 这样, 我们一开始建的树就是一个非常平衡的树, 可以使后续操作的常数更小, 并且建树整个复杂度只是 O(2n)的.
Insert 操作
其次, 我们来考虑一下如何维护一个 insert 操作. 我们可以这么做, 首先如上将需要 insert 的区间变成节点数目为 tot 的平衡树, 然后把 k+1(注意我们将需要操作的区间右移了一个单位, 所以题目所给 k 就是我们需要操作的 k+1)移到根节点的位置, 把原树中的 k+2 移到根节点的右儿子的位置. 然后把需要 insert 的区间, 先 build 成一个平衡树, 把需要 insert 的树的根直接挂到原树中 k+1 的左儿子上就行了.
Delete 操作
再然后, 我们来考虑一下 delete 操作, 我们同样的, 把需要 delete 的区间变成[k+1,k+tot](注意, 是删去 k 后面的 tot 个数, 那么可以发现我们需要操作的原区间是[k,k+tot-1]!), 然后把 k 号节点移到根节点的位置, 把 k+tot+2 移到根节点的右儿子位置, 然后直接把 k+tot+2 的左儿子的指针清为 0, 就把这段区间删掉了. 可以发现, 比 insert 还简单一点.
Reverse 操作
接下来, 这道题的重头戏就要开始了. splay 的区间操作基本原理还类似于线段树的区间操作, 即延迟修改, 又称打懒标记.
对于翻转 (reverse) 操作, 我们依旧是将操作区间变成[k+1,k+tot], 然后把 k 和 k+tot+1 分别移到对应根的右儿子的位置, 然后对这个右儿子的左儿子打上翻转标记即可.
Make-Same 操作
对于 Make-Same 操作, 我们同样需要先将需要操作的区间变成[k+1,k+tot], 然后把 k 和 k+tot+1 分别移到根和右儿子的位置, 然后对这个右儿子的左儿子打上修改标记即可.
Get-Sum 操作
对于 Get-Sum 操作, 我们还是将操作区间变成[k+1,k+tot], 然后把 k 和 k+tot+1 分别移到根和右儿子的位置, 然后直接输出这个右儿子的左儿子上的 sum 记录的和.
Max-Sum 操作
对于这个求最大子序列的操作, 即 Max-Sum 操作, 我们不能局限于最开始学最大子序列的线性 dp 方法, 而是要注意刚开始, 基本很多书都会介绍一个分治的 O(nlogn)的方法, 但是由于存在 O(n)的方法, 导致这个方法并不受重视, 但是这个方法确实很巧妙, 当数列存在修改操作时, 线性的算法就不再适用了.
这种带修改的最大子序列的问题, 最开始是由线段树来维护, 具体来说就是, 对于线段树上的每个节点所代表的区间, 维护 3 个量: lx 表示从区间左端点 l 开始的连续的前缀最大子序列. rx 表示从区间右端点 r 开始的连续的后缀最大子序列. mx 表示这个区间中的最大子序列.
那么在合并 [l,mid] 和[mid+1,r]时, 就类似一个 dp 的过程了! 其中
- lx[l,r]=max(lx[l,mid],sum[l,mid]+lx[mid+1,r])lx[l,r]=max(lx[l,mid],sum[l,mid]+lx[mid+1,r])
- rx[l,r]=max(rx[mid+1,r],sum[mid+1,r]+rx[l,mid])rx[l,r]=max(rx[mid+1,r],sum[mid+1,r]+rx[l,mid])
- mx[l,r]=max(mx[l,mid],mx[mid+1,r],lx[mid+1,r]+rx[l,mid+1])mx[l,r]=max(mx[l,mid],mx[mid+1,r],lx[mid+1,r]+rx[l,mid+1])
这个还是很好理解的. 就是选不选 mid 的两个决策. 但是其实在实现的时候, 我们并不用 [l,r] 的二维方式来记录这三个标记, 而是用对应的节点编号来表示区间, 这个可以看程序, 其实是个很简单的东西.
那么最大子序列这个询问操作就可以很简单的解决了, 还是类比前面的方法, 就是把 k 和 k+tot+1 移到对应的根和右儿子的位置, 然后直接输出右儿子的左儿子上的 mx 标记即可
懒标记的处理
最后, 相信认真看了的童鞋会有疑问, 这个标记怎么下传呢? 首先, 我们在每次将 k 和 k+tot+1 移到对应的位置时, 需要一个类似查找 k 大值的 find 操作, 即找出在平衡树中, 实际编号为 k 在树中中序遍历的编号, 这个才是我们真正需要处理的区间端点编号, 那么就好了, 我们只需在查找的过程中下传标记就好了!(其实线段树中也是这么做的), 因为我们所有的操作都需要先 find 一下, 所以我们可以保证才每次操作的结果计算出来时, 对应的节点的标记都已经传好了. 而我们在修改时, 直接修改对应节点的记录标记和懒标记, 因为我们的懒标记记录的都是已经对当前节点产生贡献, 但是还没有当前节点的子树区间产生贡献! 然后就是每处有修改的地方都要 pushup 一下就好了.
一些细节
另外, 由于本题数据空间卡的非常紧, 我们就需要用时间换空间, 直接开 4000000*logm 的数据是不现实的, 但是由于题目保证了同一时间在序列中的数字的个数最多是 500000, 所以我们考虑一个回收机制, 把用过但是已经删掉的节点编号记录到一个队列或栈中, 在新建节点时直接把队列中的冗余编号搞过来就好了.
参考代码:
- #include<bits/stdc++.h>
- #define RI register int
- #define For(i,a,b) for (RI i=a;i<=b;++i)
- using namespace std;
- const int inf=0x3f3f3f3f;
- const int N=1e6+17;
- int n,m,rt,cnt;
- int a[N],id[N],fa[N],c[N][2];
- int sum[N],sz[N],v[N],mx[N],lx[N],rx[N];
- bool tag[N],rev[N];
- //tag 表示是否有统一修改的标记, rev 表示是否有统一翻转的标记
- //sum 表示这个点的子树中的权值和, v 表示这个点的权值
- queue<int> q;
- inline int read()
- {
- RI x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
- while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
- return x*f;
- }
- inline void pushup(RI x)
- {
- RI l=c[x][0],r=c[x][1];
- sum[x]=sum[l]+sum[r]+v[x];
- sz[x]=sz[l]+sz[r]+1;
- mx[x]=max(mx[l],max(mx[r],rx[l]+v[x]+lx[r]));
- lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
- rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
- }
- // 上传记录标记
- inline void pushdown(RI x)
- {
- RI l=c[x][0],r=c[x][1];
- if(tag[x])
- {
- rev[x]=tag[x]=0;// 我们有了一个统一修改的标记, 再翻转就没有什么意义了
- if(l) tag[l]=1,v[l]=v[x],sum[l]=v[x]*sz[l];
- if(r) tag[r]=1,v[r]=v[x],sum[r]=v[x]*sz[r];
- if(v[x]>=0)
- {
- if(l) lx[l]=rx[l]=mx[l]=sum[l];
- if(r) lx[r]=rx[r]=mx[r]=sum[r];
- }
- else
- {
- if(l) lx[l]=rx[l]=0,mx[l]=v[x];
- if(r) lx[r]=rx[r]=0,mx[r]=v[x];
- }
- }
- if(rev[x])
- {
- rev[x]=0;rev[l]^=1;rev[r]^=1;
- swap(lx[l],rx[l]);swap(lx[r],rx[r]);
- // 注意, 在翻转操作中, 前后缀的最长上升子序列都反过来了, 很容易错
- swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);
- }
- }
- inline void rotate(RI x,RI &k)
- {
- RI y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
- if (y==k)k=x;else c[z][c[z][1]==y]=x;
- fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
- c[y][l]=c[x][r];c[x][r]=y;
- pushup(y);pushup(x);
- // 旋转操作, 一定要上传标记且顺序不能变
- }
- inline void splay(RI x,RI &k)
- {
- while(x!=k)
- {
- int y=fa[x],z=fa[y];
- if(y!=k)
- {
- if((c[z][0]==y)^(c[y][0]==x)) rotate(x,k);
- else rotate(y,k);
- }
- rotate(x,k);
- }
- }
- // 这是整个程序的核心之一, 毕竟是伸展操作嘛
- inline int find(RI x,RI rk)
- {// 返回当前序列第 rk 个数的标号
- pushdown(x);
- RI l=c[x][0],r=c[x][1];
- if(sz[l]+1==rk) return x;
- if(sz[l]>=rk) return find(l,rk);
- else return find(r,rk-sz[l]-1);
- }
- inline void recycle(RI x)
- {// 这就是用时间换空间的回收冗余编号机制, 很好理解
- RI &l=c[x][0],&r=c[x][1];
- if(l) recycle(l);
- if(r) recycle(r);
- q.push(x);
- fa[x]=l=r=tag[x]=rev[x]=0;
- }
- inline int split(RI k,RI tot)// 找到[k+1,k+tot]
- {
- RI x=find(rt,k),y=find(rt,k+tot+1);
- splay(x,rt);splay(y,c[x][1]);
- return c[y][0];
- }
- // 这个 split 操作是整个程序的核心之三
- // 我们通过这个 split 操作, 找到[k+1,k+tot], 并把 k, 和 k+tot+1 移到根和右儿子的位置
- // 然后我们返回了这个右儿子的左儿子, 这就是我们需要操作的区间
- inline void query(RI k,RI tot)
- {
- RI x=split(k,tot);
- printf("%d\n",sum[x]);
- }
- inline void modify(RI k,RI tot,RI val)//MAKE-SAME
- {
- RI x=split(k,tot),y=fa[x];
- v[x]=val;tag[x]=1;sum[x]=sz[x]*val;
- if(val>=0) lx[x]=rx[x]=mx[x]=sum[x];
- else lx[x]=rx[x]=0,mx[x]=val;
- pushup(y);pushup(fa[y]);
- // 每一步的修改操作, 由于父子关系发生改变
- // 及记录标记发生改变, 我们需要及时上传记录标记
- }
- inline void rever(RI k,RI tot)// 翻转
- {
- RI x=split(k,tot),y=fa[x];
- if(!tag[x])
- {
- rev[x]^=1;
- swap(c[x][0],c[x][1]);
- swap(lx[x],rx[x]);
- pushup(y);pushup(fa[y]);
- }
- // 同上
- }
- inline void erase(RI k,RI tot)//DELETE
- {
- RI x=split(k,tot),y=fa[x];
- recycle(x);c[y][0]=0;
- pushup(y);pushup(fa[y]);
- // 同上
- }
- inline void build(RI l,RI r,RI f)
- {
- RI mid=(l+r)>>1,now=id[mid],pre=id[f];
- if(l==r)
- {
- mx[now]=sum[now]=a[l];
- tag[now]=rev[now]=0;
- // 这里这个 tag 和 rev 的清 0 是必要, 因为这个编号可能是之前冗余了
- lx[now]=rx[now]=max(a[l],0);
- sz[now]=1;
- }
- if(l<mid) build(l,mid-1,mid);
- if(mid<r) build(mid+1,r,mid);
- v[now]=a[mid]; fa[now]=pre;
- pushup(now); // 上传记录标记
- c[pre][mid>=f]=now;
- // 当 mid>=f 时, now 是插入到又区间取了, 所以 c[pre][1]=now, 当 mid<f 时同理
- }
- inline void insert(RI k,RI tot)
- {
- for(int i=1;i<=tot;++i) a[i]=read();
- for(int i=1;i<=tot;++i)
- {
- if(!q.empty()) id[i]=q.front(),q.pop();
- else id[i]=++cnt;// 利用队列中记录的冗余节点编号
- }
- build(1,tot,0);
- RI z=id[(1+tot)>>1];
- RI x=find(rt,k+1),y=find(rt,k+2);
- // 首先, 依据中序遍历, 找到我们需要操作的区间的实际编号
- splay(x,rt);splay(y,c[x][1]);
- // 把 k+1(注意我们已经右移了一个单位)和(k+1)+1 移到根和右儿子
- fa[z]=y;c[y][0]=z;
- // 直接把需要插入的这个平衡树挂到右儿子的左儿子上去就好了
- pushup(y);pushup(x);
- // 上传记录标记
- }
- // 可以这么记, 只要用了 split 就要重新上传标记
- // 只有 find 中需要下传标记
- int main()
- {
- n=read(),m=read();
- mx[0]=a[1]=a[n+2]=-inf;
- For(i,1,n) a[i+1]=read();
- For(i,1,n+2) id[i]=i;// 虚拟了两个节点 1 和 n+2, 然后把需要操作区间整体右移一个单位
- build(1,n+2,0);// 建树
- rt=(n+3)>>1;cnt=n+2;// 取最中间的为根
- RI k,tot,val;char ch[10];
- while(m--)
- {
- scanf("%s",ch);
- if(ch[0]!='M' || ch[2]!='X') k=read(),tot=read();
- if(ch[0]=='I') insert(k,tot);
- if(ch[0]=='D') erase(k,tot);//DELETE
- if(ch[0]=='M')
- {
- if(ch[2]=='X') printf("%d\n",mx[rt]);//MAX-SUM
- else val=read(),modify(k,tot,val);//MAKE-SAME
- }
- if(ch[0]=='R') rever(k,tot);// 翻转
- if(ch[0]=='G') query(k,tot);//GET-SUM
- }
- return 0;
- }
- View Code
来源: https://www.cnblogs.com/songorz/p/10122047.html