树状数组
非常简单的数据结构,只需要一个数组,一切操作基于如下的函数。需要注意的是,树状数组的下标必须从1开始(从0开始会死循环)。它可以做到在O(logn)时间内完成下述的操作。
[cpp] view plain copy print ?- int bit[MAXN],n;
- inline int lowbit(int x) {
- return x&-x;
- }
最常见的是增减单点的值,询问前缀和。
[cpp] view plain copy print ?- void add(int x,int val) {
- for(int i=x; i<=n; i+=lowbit(i))
- bit[i]+=val;
- }
- int sum(int x) {
- int ret=0;
- for(int i=x; i>0; i-=lowbit(i))
- ret+=bit[i];
- return ret;
- }
我们注意到,只要维护原序列的差分序列,就可以用上述方式实现对前缀的每一位增减同一个值,询问单点值。不过,其实我们不需要手动将原数组转化为差分序列,只需对函数做一个简单的转化。
[cpp] view plain copy print ?- void add(int x,int val) {
- for(int i=x; i>0; i-=lowbit(i))
- bit[i]+=val;
- }
- int get(int x) {
- int ret=0;
- for(int i=x; i<=n; i+=lowbit(i))
- ret+=bit[i];
- return ret;
- }
树状数组其实是可以实现区间增减,区间求和的。但这个一般还是用线段树来实现。
[cpp] view plain copy print ?- //修改区间:add(r,val);
- // if(l>1) add(l-1,-val);
- //查询区间:sum(r)-sum(l-1);
- int bit1[MAXN],bit2[MAXN],n;
- void add(int x,int val) {
- for(int i=x; i>0; i-=lowbit(i))
- bit1[i]+=val;
- for(int i=x; i<=n; i+=lowbit(i))
- bit2[i]+=x*val;
- }
- int sum(int x) {
- if(!x)
- return 0;
- int ret1=0,ret2=0;
- for(int i=x; i<=n; i+=lowbit(i))
- ret1+=bit1[i];
- for(int i=x-1; i>0; i-=lowbit(i))
- ret2+=bit2[i];
- return ret1*x+ret2;
- }
树状数组也可以维护最值,但复杂度上升一个log,所以不如用线段树来维护。
[cpp] view plain copy print ?- void modify(int x,int val) {
- num[x]=val;
- for(int i=x; i<=n; i+=lowbit(i)) {
- bit[i]=max(bit[i],val);
- for(int j=1; j<lowbit(i); j<<=1)
- bit[i]=max(bit[i],bit[i-j]);
- }
- }
- int query(int L,int R) {
- int ret=num[R];
- while(true) {
- ret=max(ret,num[R]);
- if(L==R)
- break;
- for(R-=1; R-L>=lowbit(R); R-=lowbit(R))
- ret=max(ret,bit[R]);
- }
- return ret;
- }
线段树
现在最常见的线段树实现大概有两个版本,一个是NotOnlySuccess的风格,也是我最常使用的风格;它的特点是利用二叉树的数学关系来维护根节点信息。这种写法有一点不足是必须开4倍内存。支持在O(1)时间内将子树信息合并的序列信息理论上都可以用线段树来维护(如最大子段和等),区间维护依靠lazy标记完成以维持O(logn)的单次操作复杂度。
[cpp] view plain copy print ?- #define lson l,m,rt<<1
- #define rson m+1,r,rt<<1|1
- int sum[MAXN<<2],add[MAXN<<2];
- void push_up(int rt) {
- sum[rt]=sum[rt<<1]+sum[rt<<1|1];
- }
- void push_down(int rt,int len) {
- if(add[rt]) {
- add[rt<<1]+=add[rt];
- add[rt<<1|1]+=add[rt];
- sum[rt<<1]+=add[rt]*(len-(len>>1));
- sum[rt<<1|1]+=add[rt]*(len>>1);
- add[rt]=0;
- }
- }
- void build(int l,int r,int rt) {
- add[rt]=0;
- if(l==r) {
- scanf("%d",&sum[rt]);
- return;
- }
- int m=l+r>>1;
- build(lson);
- build(rson);
- push_up(rt);
- }
- void update(int p,int val,int l,int r,int rt) {
- if(l==r) {
- sum[rt]+=val;
- return;
- }
- push_down(rt,r-l+1);
- int m=l+r>>1;
- if(p<=m)
- update(p,val,lson);
- else
- update(p,val,rson);
- push_up(rt);
- }
- void update(int L,int R,int val,int l,int r,int rt) {
- if(L<=l&&r<=R) {
- add[rt]+=val;
- sum[rt]+=val*(r-l+1);
- return;
- }
- push_down(rt,r-l+1);
- int m=l+r>>1;
- if(L<=m)
- update(L,R,val,lson);
- if(m<R)
- update(L,R,val,rson);
- push_up(rt);
- }
- int query(int L,int R,int l,int r,int rt) {
- if(L<=l&&r<=R)
- return sum[rt];
- push_down(rt,r-l+1);
- int m=l+r>>1,ret=0;
- if(L<=m)
- ret+=query(L,R,lson);
- if(m<R)
- ret+=query(L,R,rson);
- return ret;
- }
另外一种有些类似,与上面不同的是,它使用下面这个神奇的ID函数组织每个节点在数组中的位置。具体实现不再赘述。
[cpp] view plain copy print ?- inline int ID(int l,int r) {
- return l+r|l!=r;
- }
可持久化线段树
如果我们想在用数据结构维护信息时,留下所有操作的历史记录,以便回退和查询,我们就需要对数据结构进行可持久化。可持久化的理念非常简单,就是把每次修改节点的操作变成新建新节点的操作,留下了原节点就留下了历史记录。
线段树是天生利于可持久化的数据结构,原因在于形态的一致性。具体地说,对于以固定方式建立的固定大小的线段树,其形态是完全一致的,且不会因修改而产生变动。为了节约空间,采用了自顶向下的函数式风格,保证了每次更新节点个数在O(logn)的级别,这个做法由黄嘉泰(fotile96)首创,故又称主席树。更具体的介绍可以看我以前的Blog,里面有很多例题,这里不再赘述。
实时开节点的线段树
我们注意到可持久化线段树常常被用来维护集合信息而非序列信息,换言之,经常以权值线段树的形式存在,其大小不由数据量决定,而是由数据的范围决定。这样我们便遇到一个困境,对于可持久化线段树这一在线维护信息的利器,却常常需要先离散化才可以使用,从实际上变成了离线做法,面对强制在线的题目非常尴尬。对此,陈立杰(WJMZBMR)在13年国家集训队论文中提到实时开节点的权值线段树;陈立杰的解释有一点抽象,我们可以这样理解,可持久化线段树是先建立初始版本的完整的树,在创建新版本时对修改的节点实时开新节点;而我们现在变成一棵初始状态为一棵空树,从一开始就实时开新节点。
即使这样说,还是显得不够具体,难以据此实现出实时开节点的线段树,所以这里以BZOJ1901为例,给出一个没有离散化,而是采用实时开节点的可持久化线段树的实现,与这里的代码做一个对比;可以发现实现起来并不麻烦。唯一美中不足是线段树部分单次操作复杂度由O(logn)升为O(logV),其中n是数据量,V是数据范围上界。
[cpp] view plain copy print ?- #include<cstdio>
- #include<cstring>
- using namespace std;
- #define lson l,m,ls[rt]
- #define rson m+1,r,rs[rt]
- const int MAXN=60005;
- const int MAXM=2500005;
- const int INF=0x3f3f3f3f;
- int ls[MAXM],rs[MAXM],cnt[MAXM],root[MAXN],tot;
- int new_node() {
- ++tot;
- ls[tot]=rs[tot]=cnt[tot]=0;
- return tot;
- }
- void update(int p,int val,int l,int r,int &rt) {
- if(!rt)
- rt=new_node();
- if(l==r) {
- cnt[rt]+=val;
- return;
- }
- int m=l+r>>1;
- if(p<=m)
- update(p,val,lson);
- else
- update(p,val,rson);
- cnt[rt]=cnt[ls[rt]]+cnt[rs[rt]];
- }
- int use[MAXN],n;
- inline int lowbit(int x) {
- return x&-x;
- }
- void modify(int x,int p,int val) {
- for(int i=x; i<=n; i+=lowbit(i))
- update(p,val,0,INF,root[i]);
- }
- int sum(int x) {
- int ret=0;
- for(int i=x; i>0; i-=lowbit(i))
- ret+=cnt[ls[use[i]]];
- return ret;
- }
- int query(int ss,int tt,int l,int r,int k) {
- for(int i=ss; i>0; i-=lowbit(i))
- use[i]=root[i];
- for(int i=tt; i>0; i-=lowbit(i))
- use[i]=root[i];
- while(l<r) {
- int m=l+r>>1,tmp=sum(tt)-sum(ss);
- if(k<=tmp) {
- r=m;
- for(int i=ss; i>0; i-=lowbit(i))
- use[i]=ls[use[i]];
- for(int i=tt; i>0; i-=lowbit(i))
- use[i]=ls[use[i]];
- } else {
- l=m+1;
- k-=tmp;
- for(int i=ss; i>0; i-=lowbit(i))
- use[i]=rs[use[i]];
- for(int i=tt; i>0; i-=lowbit(i))
- use[i]=rs[use[i]];
- }
- }
- return l;
- }
- int a[MAXN];
- int main() {
- int m,l,r,k;
- char op;
- while(~scanf("%d%d",&n,&m)) {
- tot=0;
- memset(root,0,sizeof(root));
- for(int i=1; i<=n; ++i) {
- scanf("%d",&a[i]);
- modify(i,a[i],1);
- }
- while(m--) {
- scanf(" %c%d%d",&op,&l,&r);
- switch(op) {
- case 'Q':
- scanf("%d",&k);
- printf("%d\n",query(l-1,r,0,INF,k));
- break;
- case 'C':
- modify(l,a[l],-1);
- a[l]=r;
- modify(l,a[l],1);
- break;
- }
- }
- }
- }
SkipList(跳表)
没什么用,这是我对它的评价;它能实现的一切操作用平衡二叉树都可以实现。这里放一个我测过可用,但没花心思修改的版本。
[cpp] view plain copy print ?- const int MAX_LEVEL=18;
- struct SkipList {
- struct node {
- int key,val;
- node *next[1];
- };
- int level;
- node *head;
- SkipList() {
- level=0;
- head=NewNode(MAX_LEVEL-1,0,0);
- for(int i=0; i<MAX_LEVEL; ++i)
- head->next[i]=NULL;
- }
- node* NewNode(int level,int key,int val) {
- node *ns=(node *)malloc(sizeof(node)+level*sizeof(node*));
- ns->key=key;
- ns->val=val;
- return ns;
- }
- int randomLevel() {
- int k=1;
- while(rand()&1)
- ++k;
- return k<MAX_LEVEL?k:MAX_LEVEL;
- }
- int find(int key) {
- node *p=head,*q=NULL;
- for(int i=level-1; i>=0; --i)
- while((q=p->next[i])&&q->key<=key) {
- if(q->key==key)
- return q->val;
- p=q;
- }
- return -INF;
- }
- bool insert(int key,int val) {
- node *update[MAX_LEVEL],*p=head,*q=NULL;
- for(int i=level-1; i>=0; --i) {
- while((q=p->next[i])&&q->key<key)
- p=q;
- update[i]=p;
- }
- if(q&&q->key==key)
- return false;
- int k=randomLevel();
- if(k>level) {
- for(int i=level; i<k; ++i)
- update[i]=head;
- level=k;
- }
- q=NewNode(k,key,val);
- for(int i=0; i<k; ++i) {
- q->next[i]=update[i]->next[i];
- update[i]->next[i]=q;
- }
- return true;
- }
- bool erase(int key) {
- node *update[MAX_LEVEL],*p=head,*q=NULL;
- for(int i=level-1; i>=0; --i) {
- while((q=p->next[i])&&q->key<key)
- p=q;
- update[i]=p;
- }
- if(q&&q->key==key) {
- for(int i=0; i<level; ++i)
- if(update[i]->next[i]==q)
- update[i]->next[i]=q->next[i];
- free(q);
- for(int i=level-1; i>=0; --i)
- if(head->next[i]==NULL)
- --level;
- return true;
- }
- return false;
- }
- node* getMin() {
- return head->next[0];
- }
- node* getMax() {
- node *p=head,*q=NULL;
- for(int i=level-1; i>=0; --i)
- while((q=p->next[i])&&q)
- p=q;
- return p==head?NULL:p;
- }
- };
平衡二叉树
平衡二叉树是维护集合有序性的常用数据结构。我会的平衡二叉树并不多,基本以实用为原则,有Treap、Size Balanced Tree(以下简称SBT)和Splay。它们的很多操作的实现方式完全一致或大同小异,这里为节省篇幅一并放出;注意这些操作适用于不允许重复值的平衡二叉树(set而非multiset),对于允许重复值(拥有cnt域)的实现,只要在一些+1的地方稍作修改(改成cnt[x])即可。一些使用的例题可以在这篇Blog里找到,不再赘述。
[cpp] view plain copy print ?- bool find(int v) {
- for(int x=root; x; x=ch[x][key[x]<v])
- if(key[x]==v)
- return true;
- return false;
- }
- int get_kth(int k) {
- int x=root;
- while(size[ch[x][0]]+1!=k)
- if(k<size[ch[x][0]]+1)
- x=ch[x][0];
- else {
- k-=size[ch[x][0]]+1;
- x=ch[x][1];
- }
- return key[x];
- }
- int get_rank(int v) {
- int ret=0,x=root;
- while(x)
- if(v<key[x])
- x=ch[x][0];
- else {
- ret+=size[ch[x][0]]+1;
- x=ch[x][1];
- }
- return ret;
- }
- int get_pre(int v) {
- int x=root,y=0;
- while(x)
- if(v<key[x])
- x=ch[x][0];
- else {
- y=x;
- x=ch[x][1];
- }
- return y;
- }
- int get_next(int v) {
- int x=root,y=0;
- while(x)
- if(v>key[x])
- x=ch[x][1];
- else {
- y=x;
- x=ch[x][0];
- }
- return y;
- }
- int get_min() {
- if(size[root]==0)
- return -1;
- int x=root;
- while(ch[x][0])
- x=ch[x][0];
- return x;
- }
- int get_max() {
- if(size[root]==0)
- return -1;
- int x=root;
- while(ch[x][1])
- x=ch[x][1];
- return x;
- }
- void Treaval(int x) {
- if(x) {
- Treaval(ch[x][0]);
- printf("结点%2d:左儿子 %2d 右儿子 %2d size = %2d ,val = %2d\n",x,ch[x][0],ch[x][1],size[x],key[x]);
- Treaval(ch[x][1]);
- }
- }
- void debug() {
- printf("root:%d\n",root);
- Treaval(root);
- putchar('\n');
- }
基于旋转的Treap
Treap大概是赛场上最常见的平衡二叉树,它同时维护序列的有序性和堆的性质,依靠堆值的随机化,将树的高度维护在期望下平衡的程度,从而实现了各种操作期望O(logn)的复杂度。它的性价比高在只有两种旋转(而且可以合并地写),比红黑树和AVL短小;又因为复杂度基于期望而非均摊,在各种数据下都有良好的表现。这里只给出允许重复值的实现。
[cpp] view plain copy print ?- struct Treap {
- int tot,root;
- int ch[MAXN][2],key[MAXN],pt[MAXN],cnt[MAXN],size[MAXN];
- void init() {
- tot=root=0;
- pt[0]=INF;
- }
- void push_up(int x) {
- size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
- }
- void new_node(int &x,int v) {
- x=++tot;
- ch[x][0]=ch[x][1]=0;
- size[x]=cnt[x]=1;
- pt[x]=rand();
- key[x]=v;
- }
- void rotate(int &x,int f) {
- int y=ch[x][f];
- ch[x][f]=ch[y][f^1];
- ch[y][f^1]=x;
- push_up(x);
- push_up(y);
- x=y;
- }
- void insert(int &x,int v) {
- if(!x) {
- new_node(x,v);
- return;
- }
- if(key[x]==v)
- ++cnt[x];
- else {
- int f=key[x]<v;
- insert(ch[x][f],v);
- if(pt[ch[x][f]]<pt[x])
- rotate(x,f);
- }
- push_up(x);
- }
- void erase(int &x,int v) {
- if(!x)
- return;
- if(key[x]==v) {
- if(cnt[x]>1)
- --cnt[x];
- else {
- if(!ch[x][0]&&!ch[x][1])
- x=0;
- else {
- rotate(x,pt[ch[x][0]]>pt[ch[x][1]]);
- erase(x,v);
- }
- }
- } else
- erase(ch[x][key[x]<v],v);
- push_up(x);
- }
- void insert(int v) {
- insert(root,v);
- }
- void erase(int v) {
- erase(root,v);
- }
- };
Size Balanced Tree
这个由陈启峰发明的数据结构依靠其独特的平摊时间O(1)的Maintain操作,具有仅次于红黑树的优秀的时间效率,但由于赛场上Treap已经够用,也因为有人指出陈启峰在复杂度的证明上有漏洞(有人声称某些数据可以使SBT退化成人字形,可以想象一下成串的鞭炮的样子),使用的人并不多。我也只是大致学习了一下,用的次数并不多。这里给出不允许重复值的实现。
[cpp] view plain copy print ?- struct SBT {
- int root,tot;
- int ch[MAXN][2],key[MAXN],size[MAXN];
- void init() {
- tot=root=0;
- size[0]=0;
- }
- void rotate(int &x,int f) {
- int y=ch[x][f];
- ch[x][f]=ch[y][f^1];
- ch[y][f^1]=x;
- size[y]=size[x];
- size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
- x=y;
- }
- void maintain(int &x,int f) {
- if(size[ch[ch[x][f]][f]]>size[ch[x][f^1]])
- rotate(x,f);
- else if(size[ch[ch[x][f]][f^1]]>size[ch[x][f^1]]) {
- rotate(ch[x][f],f^1);
- rotate(x,f);
- } else
- return;
- maintain(ch[x][0],0);
- maintain(ch[x][1],1);
- maintain(x,0);
- maintain(x,1);
- }
- void insert(int &x,int v) {
- if(!x) {
- x=++tot;
- ch[x][0]=ch[x][1]=0;
- size[x]=1;
- key[x]=v;
- } else {
- ++size[x];
- insert(ch[x][key[x]<v],v);
- maintain(x,key[x]<v);
- }
- }
- int erase(int &x,int v) {
- if(!x)
- return 0;
- --size[x];
- if(key[x]==v||(key[x]>v&&!ch[x][0])||(key[x]<v&&!ch[x][1])) {
- int ret=key[x];
- if(ch[x][0]&&ch[x][1])
- key[x]=erase(ch[x][0],v+1);
- else
- x=ch[x][0]+ch[x][1];
- return ret;
- }
- return erase(ch[x][key[x]<v],v);
- }
- void insert(int v) {
- insert(root,v);
- }
- void erase(int v) {
- erase(root,v);
- }
- };
Splay(伸展树)
Splay因其独特性的splay操作(将某一节点旋转到另一节点下)而得名,是一种非常灵活的,在现实生活中应用也非常广泛的二叉查找树;称之为平衡二叉树是不太严谨的,因为它从来不保证高度平衡,而是每次将访问过的节点旋转到根。也因这一操作,Splay变得异常强大,可以实现很多其它平衡树无法实现的操作(如区间翻转),它更像平衡树和线段树的杂糅,既可以维护集合信息,也可以维护序列信息,可以用它来做Treap的题,也可以用它来做线段树的题。更重要的是,Splay可以实现split(将某棵子树从原树中分离)和merge操作(将某棵子树插入另一棵树),这也使得区间插入删除成为可能。它的美中不足是常数稍大,约是Treap的1.5~3倍,线段树的2~5倍。
Splay有单旋和双旋两种实现,其中只有双旋保证了均摊O(logn)的单次操作复杂度,但因为很多人认为zigzag太长不好敲(大多是OI选手有此困扰),选择了单旋。其实完全可以稍微损失一点常数,合并成一个rotate函数来完成双旋。此外一个良好的实现通常要在序列一首一尾增加两个哨兵节点,这样可以减少很多边界特判。
有必要进行的扩展性说明是,对于一棵树,如果想要维护子树信息,我们可以用Splay维护这棵树的括号序列(dfs序),这样便可以轻易split出任意子树所属的区间;而用Splay维护dfs序的结构,就是Euler-Tour Tree。同样的,如果想要维护链上信息,可以先树链剖分然后用Splay维护每条重链,根据杨哲在07年国家集训队作业的计算,因其势能分析得到的复杂度依然是单次操作均摊O(logn)复杂度;而类似的思想做些转化,就变成了后面会提到的Link-Cut Tree(以下简称LCT)。
这里给出了POJ3580的Splay实现。注意我这次erase函数写了内存回收,这一做法完全可以照搬到其它平衡树中。
[cpp] view plain copy print ?- #include<cstdio>
- #include<algorithm>
- using namespace std;
- #define keyTree (ch[ch[root][1]][0])
- const int MAXN=200005;
- const int INF=0x3f3f3f3f;
- int num[MAXN];
- struct SplayTree {
- int root,tot1,tot2;
- int ch[MAXN][2],pre[MAXN],size[MAXN];
- int gc[MAXN],que[MAXN];
- int key[MAXN],vmin[MAXN],add[MAXN],rev[MAXN];
- void rotate(int x,int f) {
- int y=pre[x];
- ch[y][f^1]=ch[x][f];
- pre[ch[x][f]]=y;
- pre[x]=pre[y];
- if(pre[x])
- ch[pre[y]][ch[pre[y]][1]==y]=x;
- ch[x][f]=y;
- pre[y]=x;
- push_up(y);
- }
- void splay(int x,int goal) {
- push_down(x);
- while(pre[x]!=goal) {
- int y=pre[x],z=pre[y];
- if(z==goal) {
- push_down(y);
- push_down(x);
- rotate(x,ch[y][0]==x);
- } else {
- push_down(z);
- push_down(y);
- push_down(x);
- int f=ch[z][0]==y;
- if(ch[y][f]==x)
- rotate(x,f^1);
- else
- rotate(y,f);
- rotate(x,f);
- }
- }
- push_up(x);
- if(goal==0)
- root=x;
- }
- void rotate_to(int k,int goal) {
- int x=root;
- push_down(x);
- while(size[ch[x][0]]!=k) {
- if(k<size[ch[x][0]])
- x=ch[x][0];
- else {
- k-=size[ch[x][0]]+1;
- x=ch[x][1];
- }
- push_down(x);
- }
- splay(x,goal);
- }
- void erase(int x) {
- int fa=pre[x],head=0,tail=0;
- for(que[tail++]=x; head<tail; ++head) {
- gc[tot2++]=que[head];
- if(ch[que[head]][0])
- que[tail++]=ch[que[head]][0];
- if(ch[que[head]][1])
- que[tail++]=ch[que[head]][1];
- }
- ch[fa][ch[fa][1]==x]=0;
- push_up(fa);
- }
- void new_node(int &x,int v,int fa) {
- if(tot2)
- x=gc[--tot2];
- else
- x=++tot1;
- ch[x][0]=ch[x][1]=0;
- pre[x]=fa;
- size[x]=1;
- key[x]=vmin[x]=v;
- add[x]=rev[x]=0;
- }
- void update_add(int x,int d) {
- if(x) {
- key[x]+=d;
- add[x]+=d;
- vmin[x]+=d;
- }
- }
- void update_rev(int x) {
- if(x) {
- swap(ch[x][0],ch[x][1]);
- rev[x]^=1;
- }
- }
- void push_up(int x) {
- size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
- vmin[x]=min(key[x],min(vmin[ch[x][0]],vmin[ch[x][1]]));
- }
- void push_down(int x) {
- if(add[x]) {
- update_add(ch[x][0],add[x]);
- update_add(ch[x][1],add[x]);
- add[x]=0;
- }
- if(rev[x]) {
- update_rev(ch[x][0]);
- update_rev(ch[x][1]);
- rev[x]=0;
- }
- }
- void build(int &x,int l,int r,int f) {
- int m=l+r>>1;
- new_node(x,num[m],f);
- if(l<m)
- build(ch[x][0],l,m-1,x);
- if(r>m)
- build(ch[x][1],m+1,r,x);
- push_up(x);
- }
- void init(int n) {
- root=tot1=tot2=0;
- ch[0][0]=ch[0][1]=pre[0]=size[0]=0;
- add[0]=rev[0]=0;
- key[0]=vmin[0]=INF;
- new_node(root,-1,0);
- new_node(ch[root][1],-1,root);
- size[root]=2;
- for(int i=1; i<=n; ++i)
- scanf("%d",&num[i]);
- build(keyTree,1,n,ch[root][1]);
- push_up(ch[root][1]);
- push_up(root);
- }
- void plus(int l,int r,int v) {
- rotate_to(l-1,0);
- rotate_to(r+1,root);
- update_add(keyTree,v);
- }
- void reverse(int l,int r) {
- rotate_to(l-1,0);
- rotate_to(r+1,root);
- update_rev(keyTree);
- }
- void revolve(int l,int r,int k) {
- k%=r-l+1;
- if(!k)
- return;
- rotate_to(r-k,0);
- rotate_to(r+1,root);
- int tmp=keyTree;
- keyTree=0;
- push_up(ch[root][1]);
- push_up(root);
- rotate_to(l-1,0);
- rotate_to(l,root);
- keyTree=tmp;
- pre[tmp]=ch[root][1];
- push_up(ch[root][1]);
- push_up(root);
- }
- void insert(int k,int v) {
- rotate_to(k,0);
- rotate_to(k+1,root);
- new_node(keyTree,v,ch[root][1]);
- push_up(ch[root][1]);
- push_up(root);
- }
- void del(int k) {
- rotate_to(k-1,0);
- rotate_to(k+1,root);
- erase(keyTree);
- push_up(ch[root][1]);
- push_up(root);
- }
- int query(int l,int r) {
- rotate_to(l-1,0);
- rotate_to(r+1,root);
- return vmin[keyTree];
- }
- } splay;
- int main() {
- int n,m,x,y,v;
- char op[10];
- while(~scanf("%d",&n)) {
- splay.init(n);
- scanf("%d",&m);
- while(m--) {
- scanf("%s",op);
- switch(op[0]) {
- case 'A':
- scanf("%d%d%d",&x,&y,&v);
- splay.plus(x,y,v);
- break;
- case 'R':
- scanf("%d%d",&x,&y);
- if(op[3]=='E')
- splay.reverse(x,y);
- else {
- scanf("%d",&v);
- splay.revolve(x,y,v);
- }
- break;
- case 'I':
- scanf("%d%d",&x,&v);
- splay.insert(x,v);
- break;
- case 'D':
- scanf("%d",&x);
- splay.del(x);
- break;
- case 'M':
- scanf("%d%d",&x,&y);
- printf("%d\n",splay.query(x,y));
- break;
- }
- }
- }
- }
额外的更新。哨兵节点的存在有利有弊,在对树进行split和merge的时候有时会出现一些调试上的不便,在某些时候显得代码不够优雅。由此,我参照交大板,结合LCT的一些函数写了新的实现。以下是HDU4453的Splay实现,当然用上面的做法和后面提到的不基于旋转的Treap同样可做。
[cpp] view plain copy print ?- #include<cstdio>
- #include<algorithm>
- using namespace std;
- const int MAXN=200005;
- int k1,k2,num[MAXN];
- struct Splay {
- int root,tot,point;
- int ch[MAXN][2],pre[MAXN],size[MAXN];
- int key[MAXN],add[MAXN],rev[MAXN];
- bool isroot(int x) {
- return !pre[x]||ch[pre[x]][0]!=x&&ch[pre[x]][1]!=x;
- }
- void rotate(int x) {
- int y=pre[x],f=ch[y][1]==x;
- ch[y][f]=ch[x][f^1];
- pre[ch[y][f]]=y;
- if(!isroot(y))
- ch[pre[y]][ch[pre[y]][1]==y]=x;
- pre[x]=pre[y];
- ch[x][f^1]=y;
- pre[y]=x;
- push_up(y);
- }
- void splay(int x) {
- push_down(x);
- while(!isroot(x)) {
- int y=pre[x],z=pre[y];
- if(isroot(y)) {
- push_down(y);
- push_down(x);
- rotate(x);
- } else {
- push_down(z);
- push_down(y);
- push_down(x);
- rotate((ch[z][1]==y)==(ch[y][1]==x)?y:x);
- rotate(x);
- }
- }
- push_up(x);
- }
- void new_node(int &x,int v,int fa) {
- x=++tot;
- ch[x][0]=ch[x][1]=0;
- pre[x]=fa;
- size[x]=1;
- key[x]=v;
- add[x]=rev[x]=0;
- }
- void update_add(int x,int v) {
- if(x) {
- key[x]+=v;
- add[x]+=v;
- }
- }
- void update_rev(int x) {
- if(x) {
- rev[x]^=1;
- swap(ch[x][0],ch[x][1]);
- }
- }
- void push_down(int x) {
- if(add[x]) {
- update_add(ch[x][0],add[x]);
- update_add(ch[x][1],add[x]);
- add[x]=0;
- }
- if(rev[x]) {
- update_rev(ch[x][0]);
- update_rev(ch[x][1]);
- rev[x]=0;
- }
- }
- void push_up(int x) {
- size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
- }
- void build(int &x,int l,int r,int fa) {
- int m=l+r>>1;
- new_node(x,num[m],fa);
- if(l<m)
- build(ch[x][0],l,m-1,x);
- if(r>m)
- build(ch[x][1],m+1,r,x);
- push_up(x);
- }
- void init(int n) {
- root=tot=size[0]=0;
- for(int i=1; i<=n; ++i)
- scanf("%d",&num[i]);
- build(root,1,n,0);
- point=1;
- }
- int find(int rt,int k) {
- int x=rt;
- while(size[ch[x][0]]+1!=k) {
- push_down(x);
- if(k<=size[ch[x][0]])
- x=ch[x][0];
- else {
- k-=size[ch[x][0]]+1;
- x=ch[x][1];
- }
- }
- return x;
- }
- void split(int &x,int &y,int sz) {
- if(!sz) {
- y=x;
- x=0;
- return;
- }
- y=find(x,sz+1);
- splay(y);
- x=ch[y][0];
- ch[y][0]=0;
- push_up(y);
- }
- void split3(int &x,int &y,int &z,int l,int r) {
- split(x,z,r);
- split(x,y,l-1);
- }
- void join(int &x,int &y) {
- if(!x||!y) {
- x|=y;
- return;
- }
- x=find(x,size[x]);
- splay(x);
- ch[x][1]=y;
- pre[y]=x;
- push_up(x);
- }
- void join3(int &x,int y,int z) {
- join(y,z);
- join(x,y);
- }
- void evert() {
- if(point>1) {
- int x;
- split(root,x,point-1);
- swap(root,x);
- join(root,x);
- point=1;
- }
- }
- void plus(int v) {
- evert();
- int x,y;
- split3(root,x,y,point,point+k2-1);
- update_add(x,v);
- join3(root,x,y);
- }
- void reverse() {
- evert();
- int x,y;
- split3(root,x,y,point,point+k1-1);
- update_rev(x);
- join3(root,x,y);
- }
- void insert(int v) {
- evert();
- int x,y;
- split(root,x,point);
- new_node(y,v,0);
- join3(root,y,x);
- }
- void erase() {
- evert();
- int x,y;
- split3(root,x,y,point,point);
- join(root,y);
- }
- void move(int tag) {
- switch(tag) {
- case 1:
- if(--point==0)
- point=size[root];
- break;
- case 2:
- if(++point==size[root]+1)
- point=1;
- break;
- }
- }
- void query() {
- evert();
- int x,y;
- split3(root,x,y,point,point);
- printf("%d\n",key[x]);
- join3(root,x,y);
- }
- } splay;
- int main() {
- int n,m,v,cas=0;
- char op[10];
- while(~scanf("%d%d%d%d",&n,&m,&k1,&k2)&&(n||m||k1||k2)) {
- splay.init(n);
- printf("Case #%d:\n",++cas);
- while(m--) {
- scanf("%s",op);
- switch(op[0]) {
- case 'a':
- scanf("%d",&v);
- splay.plus(v);
- break;
- case 'r':
- splay.reverse();
- break;
- case 'i':
- scanf("%d",&v);
- splay.insert(v);
- break;
- case 'd':
- splay.erase();
- break;
- case 'm':
- scanf("%d",&v);
- splay.move(v);
- break;
- case 'q':
- splay.query();
- break;
- }
- }
- }
- }
Link-Cut Tree
动态树是维护森林信息的一类问题的总称。最常见的也是我唯一会的就是LCT;此外还有自适应Top Tree、全局平衡二叉树等。LCT可以维护多棵树(森林)的形态,并在O(logn)的时间复杂度内维护链上信息;但LCT处理子树信息将会非常麻烦。它的核心操作是access函数,可以把某个节点到根的路径上所有点按照深度用Splay维护起来,从而结合evert函数(换跟操作)和splay操作可以实现对链的信息维护。LCT几乎可以实现除维护子树信息外以上的所有操作,同时有着优越的理论复杂度,但实际常数较大,很多不改变树形态的题用O(logn)的LCT并不比O(log^2n)的树链剖分套线段树更优越。以下是HDU4010的LCT实现。
[cpp] view plain copy print ?- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int MAXN=300005;
- struct LCT {
- int ch[MAXN][2],pre[MAXN],key[MAXN],rev[MAXN];
- int add[MAXN],vmax[MAXN];
- bool isroot(int x) {
- return !pre[x]||ch[pre[x]][0]!=x&&ch[pre[x]][1]!=x;
- }
- void rotate(int x) {
- int y=pre[x],f=ch[y][1]==x;
- ch[y][f]=ch[x][f^1];
- pre[ch[y][f]]=y;
- if(!isroot(y))
- ch[pre[y]][ch[pre[y]][1]==y]=x;
- pre[x]=pre[y];
- ch[x][f^1]=y;
- pre[y]=x;
- push_up(y);
- }
- void splay(int x) {
- push_down(x);
- while(!isroot(x)) {
- int y=pre[x],z=pre[y];
- if(isroot(y)) {
- push_down(y);
- push_down(x);
- rotate(x);
- } else {
- push_down(z);
- push_down(y);
- push_down(x);
- rotate((ch[z][1]==y)==(ch[y][1]==x)?y:x);
- rotate(x);
- }
- }
- push_up(x);
- }
- int access(int x) {
- int y=0;
- for(; x; x=pre[x]) {
- splay(x);
- ch[x][1]=y;
- push_up(x);
- y=x;
- }
- return y;
- }
- void evert(int x) {
- rev[access(x)]^=1;
- splay(x);
- }
- void push_up(int x) {
- vmax[x]=max(max(vmax[ch[x][0]],vmax[ch[x][1]]),key[x]);
- }
- void push_down(int x) {
- if(add[x]) {
- key[x]+=add[x];
- if(ch[x][0]) {
- add[ch[x][0]]+=add[x];
- vmax[ch[x][0]]+=add[x];
- }
- if(ch[x][1]) {
- add[ch[x][1]]+=add[x];
- vmax[ch[x][1]]+=add[x];
- }
- add[x]=0;
- }
- if(rev[x]) {
- if(ch[x][0])
- rev[ch[x][0]]^=1;
- if(ch[x][1])
- rev[ch[x][1]]^=1;
- swap(ch[x][0],ch[x][1]);
- rev[x]=0;
- }
- }
- int find_root(int x) {
- while(pre[x])
- x=pre[x];
- return x;
- }
- void link(int u,int v) {
- if(find_root(u)==find_root(v)) {
- puts("-1");
- return;
- }
- evert(u);
- pre[u]=v;
- }
- void cut(int u,int v) {
- if(u==v||find_root(u)!=find_root(v)) {
- puts("-1");
- return;
- }
- evert(u);
- access(v);
- splay(v);
- pre[ch[v][0]]=0;
- ch[v][0]=0;
- push_up(v);
- }
- void update(int u,int v,int w) {
- if(find_root(u)!=find_root(v)) {
- puts("-1");
- return;
- }
- evert(u);
- access(v);
- splay(v);
- add[v]+=w;
- vmax[v]+=w;
- push_down(v);
- }
- void query(int u,int v) {
- if(find_root(u)!=find_root(v)) {
- puts("-1");
- return;
- }
- evert(u);
- access(v);
- splay(v);
- printf("%d\n",vmax[v]);
- }
- struct graph {
- int head[MAXN],to[MAXN<<1],next[MAXN<<1];
- int tot;
- void init() {
- tot=0;
- memset(head,0xff,sizeof(head));
- }
- void add(int u,int v) {
- to[tot]=v;
- next[tot]=head[u];
- head[u]=tot++;
- }
- } g;
- void dfs(int u,int fa) {
- for(int i=g.head[u]; ~i; i=g.next[i]) {
- int v=g.to[i];
- if(v!=fa) {
- dfs(v,u);
- pre[v]=u;
- }
- }
- }
- void init(int n) {
- int m,x,y;
- g.init();
- for(int i=1; i<n; ++i) {
- scanf("%d%d",&x,&y);
- g.add(x,y);
- g.add(y,x);
- }
- memset(ch,0,sizeof(ch));
- memset(pre,0,sizeof(pre));
- memset(rev,0,sizeof(rev));
- memset(add,0,sizeof(add));
- vmax[0]=0;
- for(int i=1; i<=n; ++i) {
- scanf("%d",&key[i]);
- vmax[i]=key[i];
- }
- dfs(1,0);
- }
- } lct;
- int main() {
- int n,q,op,x,y,w;
- while(~scanf("%d",&n)) {
- lct.init(n);
- scanf("%d",&q);
- while(q--) {
- scanf("%d",&op);
- switch(op) {
- case 1:
- scanf("%d%d",&x,&y);
- lct.link(x,y);
- break;
- case 2:
- scanf("%d%d",&x,&y);
- lct.cut(x,y);
- break;
- case 3:
- scanf("%d%d%d",&w,&x,&y);
- lct.update(x,y,w);
- break;
- case 4:
- scanf("%d%d",&x,&y);
- lct.query(x,y);
- break;
- }
- }
- putchar('\n');
- } }
- }
更多推荐
常用数据结构小结
发布评论