区间树学习总结——[NOI2005]维护数列
hyfhaha
2019-04-17 20:50:22
区间树这玩意真TM玄学。我是不是也应该说一声.
# 无指针超详细Splay讲解
## 学这东西你必须要拥有的
1.通过[【模板】文艺平衡树（Splay）](https://www.luogu.org/problemnew/show/P3391)，[【模板】普通平衡树](https://www.luogu.org/problemnew/show/P3369)，[GSS3 - Can you answer these queries III](https://www.luogu.org/problemnew/show/SP1716).
2.学会Splay，学会求最大子段和并知道怎么维护信息和下传标记，及会有区间修的最大子段和.
3.~~多年的编程技巧~~，以及一颗写数据结构的良好心态.
4.攒够~~两个月的~~肝，这很重要！
## 如果你不会上面东西的解决方法
1.看以下博客[Splay入门解析](https://www.cnblogs.com/cjyyb/p/7499020.html)，[文艺平衡树Splay题解](https://www.luogu.org/blog/cjyyb/solution-p3391)，[GSS系列题解——最大子段和系列](https://www.luogu.org/blog/juruohyfhaha/gss-ji-lie-ti-xie-zui-tai-zi-duan-hu-ji-lie)。
2.看上面.
3.别管，瞎逼的.
4.好好养生，如果不够肝的话千万别写这道题.
# 那么现在就可以开始了
既然你已经会了上面的前置技能，那么我们就可以开始**分步**解决这道题了。
先给出我们需要存的全部信息：
```cpp
struct kkk{
int ch[2]; //左右儿子
int size; //子树大小
int fa; //父亲
int tag; //赋值标记
int val; //权值
int rev; //翻转标记
int sum; //区间权值和
int left; //左区间，指区间最大前缀和
int right; //右区间，指区间最大后缀和
int middle; //中区间，指区间最大子段和
void clear(){ch[0]=ch[1]=fa=rev=0;tag=TAGNONE;} //清空节点信息
}tree[maxn];
```
存的东西很多，大家务必要理解清楚每一个信息所表达的含义。
# 区间树Splay介绍
做过“普通平衡树”的都知道，在“普通平衡树”里，Splay是按照权值来排序的，所以能维护数的关系。那么现在到了维护区间上的操作了，也就不能按权值来排序了。
区间树，我们按照的是序列中的**编号**来排序。
我们可以发现，序列中的第**k**个点，在Splay中也是第**k**大的。（按编号排序嘛.
所以我们想要查找序列中第**k**个位置，就直接找**Splay**中的第**k**大就可以了。
所以“普通平衡树”里的**Splay**操作，**rotate**操作和**kth**操作都是可以直接照搬的（一样的，只是维护编号而已.
那么我们怎么在Splay中找到一个区间[x,y]呢？
我们可以考虑Splay的性质，将 **x** Splay上根，再将 **y** Splay上到x的右节点，那么我们得出的 **y** 的左子树就是我们要的[x,y]区间。
之后我们想对这个区间做什么就可以直接对那颗子树做了。
上面就是区间树的一些介绍.
### 代码中的一些宏定义
```cpp
#define TAGNONE 10000001 //没有赋值tag的标志
#define L(node) (tree[node].ch[0]) //替左儿子
#define R(node) (tree[node].ch[1]) //替右儿子
#define F(node) (tree[node].fa) //替父亲
#define V(node) (tree[node].val) //替权值
#define S(node) (tree[node].size) //替子树大小
#define compare(node,x) (tree[node].val<x) //比较node是权值x的左儿子还是右儿子
```
# 操作剖析
## 1.基本操作 Splay,rotate,kth
这个就不用怎么说了吧，大家在做平衡树Splay都写过的啦！
## 2.将指定区间找出来 split操作
和上面讲的区间树一样，先找到区间[l,r]的kth，计**l**的kth为**x**，**r**的kth为**y**。
然后Splay(x,0);Splay(y,x); （直接上代码解释).
最后返回**y**的**左儿子**就是指定区间.
代码：
```cpp
int split(int k,int len){ //找到那个区间的位置
int x=kth(k),y=kth(k+len+1);
Splay(x,0);Splay(y,x);
return L(y);
}
```
## 3.建一颗平衡的Splay，build操作
一开始我们要构造一颗有初始信息的Splay，一个一个insert显然很慢，所以我们写一个build，可以将一段序列建成一颗平衡的Splay的操作。
其实写起来和线段树差不多，注意是以**编号**排序来建树。
```cpp
void New(int node,int x){ //新建节点
tree[node].middle=tree[node].sum=x; //赋值信息
tree[node].tag=TAGNONE;tree[node].rev=0; //标记初始化
tree[node].left=tree[node].right=max(x,0); //区间赋值
tree[node].size=1; //大小赋值
}
void build(int begin,int end,int fa){ //建树
int mid=(begin+end)>>1;int node=id[mid],pre=id[fa];
if(begin==end) //到达底部
New(node,a[begin]); //新建一个节点
if(begin<mid)build(begin,mid-1,mid); //建左子树
if(mid<end)build(mid+1,end,mid); //建右子树
tree[node].val=a[mid];tree[node].fa=pre;tree[node].tag=TAGNONE; //基本信息赋值
pushup(node); //维护信息
tree[pre].ch[mid>=fa]=node;
}
```
## 4.插入操作 insert
这里题目要求的是在x位置后插入一段长为len的序列.
如果我们还是一个一个插入，仍然很慢，所以我们可以直接把插入的序列build成一颗平衡的子树，最后直接在x后插入建成的子树就可以了。
```cpp
void insert(int k,int len){ //插入区间
for(int i=1;i<=len;i++)scanf("%d",&a[i]); //输入区间
for(int i=1;i<=len;i++)
id[i]=rublish(); //从垃圾桶里找一个编号
build(1,len,0); //将输入的区间建成一个完全二叉树
int z=id[(1+len)>>1];
int x=kth(k+1),y=kth(k+2); //找到要插入的位置
Splay(x,0);Splay(y,x);
tree[z].fa=y; tree[y].ch[0]=z; //将新建的子树插入树中
pushup(y);pushup(x); //维护信息
}
```
## 5.删除操作 eraser
这个就更简单了，直接找到那个区间，然后让那个子树的父亲将左儿子清为0就可以了。
但是，为了节省空间，我们加入了一个垃圾回收的操作，就是将删除的节点重新利用起来，以节省空间.
所以我们还要遍历一遍子树将那颗子树的节点扔进垃圾桶里.
```cpp
int rublish(){ //垃圾回收
if(top==0)return ++cnt;
int node=rub[top--];
return node;
}
void remove(int node){ //将一个子树清空
if(L(node))remove(L(node)); //继续清空左子树
if(R(node))remove(R(node)); //继续清空右子树
rub[++top]=node; tree[node].clear(); //清空并仍进垃圾桶，定义里有
}
void eraser(int x,int len){ //删除区间
int node=split(x,len),y=F(node);//找到该区间
remove(node);tree[y].ch[0]=0; //删除该区间，子树清空
pushup(y);pushup(F(y)); //维护信息
}
```
## 6.修改操作 update
一样的，先找到指定区间的子树，然后直接修改信息，打上赋值标记.
```cpp
void change_val(int node,int val){ //更新点值
if(!node)return ; //空节点返回
tree[node].tag=tree[node].val=val; //打赋值标记，更新权值
tree[node].sum=val*tree[node].size; //更新区间权值和
tree[node].left=tree[node].right=max(tree[node].sum,0); //左右区间更新
tree[node].middle=max(tree[node].sum,val); //最大子段和更新
}
void update(int x,int len,int val){ //更新区间的指
int node=split(x,len),y=F(node); //找到该区间
change_val(node,val); //更新该区间
pushup(y);pushup(F(y)); //维护信息
}
```
## 7.翻转操作 reverse
一样的，先找到指定的区间的子树，然后直接翻转，打上翻转标记.
```cpp
void change_rev(int node){ //更新翻转
swap(tree[node].ch[0],tree[node].ch[1]);//交换左右儿子
swap(tree[node].left,tree[node].right); //交换左右区间
tree[node].rev^=1; //打翻转标记
}
void reverse(int x,int len){ //翻转区间
int node=split(x,len),y=F(node);//找到该区间
if(tree[node].tag!=TAGNONE)return ; //如果已经有赋值标记就不用管了
change_rev(node); //翻转该区间
pushup(y);pushup(F(y)); //维护信息
}
```
## 8.求和操作 query
这就更简单了，找到指定区间的子树，然后直接输出那颗子树的sum就OK了.
```cpp
void query(int x,int len){ //查询区间权值和
int node=split(x,len); //找到该区间
printf("%d\n",tree[node].sum); //输出答案
}
```
## 9.求最大子段和
直接输出root的middle最大子段和.
```cpp
printf("%d\n",tree[root].middle);
```
# 难点
## 10.维护信息和下传标记
这玩意是真毒瘤，不过主要还是难在最大子段和上面，只要我们能理解“GSS3”中的求法，其实也很简单。
维护信息，所以除了这个最大子段和之外，好像还挺简单的。最大子段和那几个更新方法这里就不讲了，不知道可以看上面的博客。
```cpp
void pushup(int node){ //维护信息
kkk &x=tree[L(node)],&y=tree[R(node)];int val=tree[node].val; //实质是将左右儿子合并，x代替左儿子，y代替右儿子
kkk &res=tree[node]; //res代替tree[node]
res.sum=x.sum+y.sum+val; res.size=x.size+y.size+1; //权值和更新，子树大小更新
res.middle=max(max(x.middle,y.middle),x.right+y.left+val); //最大子段和更新
res.left=max(x.left,x.sum+y.left+val); //区间最大前缀和更新
res.right=max(y.right,y.sum+x.right+val); //区间最大后缀和更新
}
```
下传标记，这本来是比较得毒瘤，我们要先更新赋值操作，左右儿子有很多信息需要更新，其中就有tag，sum，left，right和middle，更新起来十分的繁琐。但是在之前的赋值操作update中，我们引入了一个叫change_val的函数，所以这里，我们可以直接调用那个函数。于是代码就被减短了很多。
最后将tag标记为TAGNONE就OK了.
然后要更新翻转操作，一样的，在之前翻转操作revrese中，我们引入了一个叫change_rev的函数，所以这里，我们还是可以直接调用。于是代码又被减了……
最后将rev标记为0就OK了。
代码：
```cpp
void pushdown(int node){ //标记下传
if(tree[node].tag!=TAGNONE){ //判断有没有赋值标记
change_val(L(node),tree[node].tag); //更新左儿子
change_val(R(node),tree[node].tag); //更新右儿子
tree[node].tag=TAGNONE; //除去标记
}
if(tree[node].rev){ //判断有没有翻转标记
change_rev(L(node)); //更新左儿子
change_rev(R(node)); //更新右儿子
tree[node].rev=0; //除去标记
}
}
```
看，多简短!
## 11.主函数
注意边界！注意边界！注意边界！ 主要的事情说三遍！
其他就没什么了，都是输入嘛。
# 总代码
```cpp
#include<bits/stdc++.h>
#define TAGNONE 10000001
#define maxn 1000010
#define inf 100000001
#define L(node) (tree[node].ch[0]) //替左儿子
#define R(node) (tree[node].ch[1]) //替右儿子
#define F(node) (tree[node].fa) //替父亲
#define V(node) (tree[node].val) //替权值
#define S(node) (tree[node].size) //替子树大小
#define compare(node,x) (tree[node].val<x) //比较node是权值x的左儿子还是右儿子
using namespace std;
int root,cnt,a[maxn],id[maxn],rub[maxn],top,n,m;
struct kkk{
int ch[2]; //左右儿子
int size; //子树大小
int fa; //父亲
int tag; //赋值标记
int val; //权值
int rev; //翻转标记
int sum; //区间权值和
int left; //左区间，指区间最大前缀和
int right; //右区间，指区间最大后缀和
int middle; //中区间，指区间最大子段和
void clear(){ch[0]=ch[1]=fa=rev=0;tag=TAGNONE;} //清空节点信息
}tree[maxn];
int rublish(){ //垃圾回收
if(top==0)return ++cnt;
int node=rub[top--];
return node;
}
void change_val(int node,int val){ //更新点值
if(!node)return ; //空节点返回
tree[node].tag=tree[node].val=val; //打赋值标记，更新权值
tree[node].sum=val*tree[node].size; //更新区间权值和
tree[node].left=tree[node].right=max(tree[node].sum,0); //左右区间更新
tree[node].middle=max(tree[node].sum,val); //最大子段和更新
}
void change_rev(int node){ //更新翻转
swap(tree[node].ch[0],tree[node].ch[1]);//交换左右儿子
swap(tree[node].left,tree[node].right); //交换左右区间
tree[node].rev^=1; //打翻转标记
}
void pushup(int node){ //维护信息
kkk &x=tree[L(node)],&y=tree[R(node)];int val=tree[node].val; //实质是将左右儿子合并，x代替左儿子，y代替右儿子
kkk &res=tree[node]; //res代替tree[node]
res.sum=x.sum+y.sum+val;res.size=x.size+y.size+1; //权值和更新，子树大小更新
res.middle=max(max(x.middle,y.middle),x.right+y.left+val); //最大子段和更新
res.left=max(x.left,x.sum+y.left+val); //区间最大前缀和更新
res.right=max(y.right,y.sum+x.right+val); //区间最大后缀和更新
}
void pushdown(int node){ //标记下传
if(tree[node].tag!=TAGNONE){ //判断有没有赋值标记
change_val(L(node),tree[node].tag); //更新左儿子
change_val(R(node),tree[node].tag); //更新右儿子
tree[node].tag=TAGNONE; //除去标记
}
if(tree[node].rev){ //判断有没有翻转标记
change_rev(L(node)); //更新左儿子
change_rev(R(node)); //更新右儿子
tree[node].rev=0; //除去标记
}
}
void rotate(int node){ //rotate 模板
int fa=F(node);
int gfa=F(fa);
int z=tree[fa].ch[1]==node;
tree[gfa].ch[tree[gfa].ch[1]==fa]=node; tree[node].fa=gfa;
tree[fa].ch[z]=tree[node].ch[z^1];tree[tree[node].ch[z^1]].fa=fa;
tree[node].ch[z^1]=fa;tree[fa].fa=node;
pushup(fa); pushup(node);
}
void Splay(int node,int goal){ //Splay 模板
while(tree[node].fa!=goal){
int fa=F(node);
int gfa=F(fa);
if(gfa!=goal)
(compare(fa,tree[node].val))!=(compare(gfa,tree[fa].val))
?rotate(node) : rotate(fa);
rotate(node);
}
if(!goal)root=node;
}
void New(int node,int x){ //新建节点
tree[node].middle=tree[node].sum=x; //赋值信息
tree[node].tag=TAGNONE;tree[node].rev=0; //标记初始化
tree[node].left=tree[node].right=max(x,0); //区间赋值
tree[node].size=1; //大小赋值
}
void build(int begin,int end,int fa){ //建树
int mid=(begin+end)>>1;int node=id[mid],pre=id[fa];
if(begin==end) //到达底部
New(node,a[begin]); //新建一个节点
if(begin<mid)build(begin,mid-1,mid); //建左子树
if(mid<end)build(mid+1,end,mid); //建右子树
tree[node].val=a[mid];tree[node].fa=pre;tree[node].tag=TAGNONE; //基本信息赋值
pushup(node); //维护信息
tree[pre].ch[mid>=fa]=node;
}
int kth(int x){ //kth模板
int node=root;
while(1){
pushdown(node);
if(tree[L(node)].size>=x)node=L(node);
else
if(tree[L(node)].size+1==x)return node;
else x-=tree[L(node)].size+1,node=R(node);
}
}
void remove(int node){ //将一个子树清空
if(L(node))remove(L(node)); //继续清空左子树
if(R(node))remove(R(node)); //继续清空右子树
rub[++top]=node; tree[node].clear(); //清空并仍进垃圾桶
}
int split(int k,int len){ //找到那个区间的位置
int x=kth(k),y=kth(k+len+1);
Splay(x,0);Splay(y,x);
return L(y);
}
void query(int x,int len){ //查询区间权值和
int node=split(x,len); //找到该区间
printf("%d\n",tree[node].sum); //输出答案
}
void update(int x,int len,int val){ //更新区间的指
int node=split(x,len),y=F(node); //找到该区间
change_val(node,val); //更新该区间
pushup(y);pushup(F(y)); //维护信息
}
void rever(int x,int len){ //翻转区间
int node=split(x,len),y=F(node);//找到该区间
if(tree[node].tag!=TAGNONE)return ; //如果已经有赋值标记就不用管了
change_rev(node); //翻转该区间
pushup(y);pushup(F(y)); //维护信息
}
void eraser(int x,int len){ //删除区间
int node=split(x,len),y=F(node);//找到该区间
remove(node);tree[y].ch[0]=0; //删除该区间，子树清空
pushup(y);pushup(F(y)); //维护信息
}
void insert(int k,int len){ //插入区间
for(int i=1;i<=len;i++)scanf("%d",&a[i]); //输入区间
for(int i=1;i<=len;i++)
id[i]=rublish();
build(1,len,0); //将输入的区间建成一个完全二叉树
int z=id[(1+len)>>1];
int x=kth(k+1),y=kth(k+2); //找到要插入的位置
Splay(x,0);Splay(y,x);
tree[z].fa=y; tree[y].ch[0]=z; //将新建的子树插入树中
pushup(y);pushup(x); //维护信息
}
int main(){
scanf("%d%d",&n,&m);
tree[0].middle=a[1]=a[n+2]=-inf; //边界
for(int i=1;i<=n;i++)scanf("%d",&a[i+1]); //输入
for(int i=1;i<=n+2;i++)id[i]=i;
build(1,n+2,0); //建成一颗Splay
root=(n+3)>>1;cnt=n+2; //指根，更新点数
for(int i=1;i<=m;i++){
string s; int x,len,y;
cin>>s;
if(s!="MAX-SUM")scanf("%d%d",&x,&len);
else printf("%d\n",tree[root].middle);
if(s=="INSERT")insert(x,len);
if(s=="DELETE")eraser(x,len);
if(s=="MAKE-SAME")
scanf("%d",&y),update(x,len,y);
if(s=="REVERSE")rever(x,len);
if(s=="GET-SUM")query(x,len);
}
}
```
## 后记
学习时有参考[I_AM_HelloWord](https://www.luogu.org/space/show?uid=54916)大佬的题解。所以有的地方和他的代码很像。
希望大家都能掌握区间树QwQ。
# 谢谢观赏