【转】动态树

动态树是一种“超级数据结构”，它能够维护一个由若干有根树组成的森林，在对数的时间复杂度内支持：

1.查询一个点的父亲

2.查询一个点所在的树的根

3.修改某个节点的权

4.向从某个节点到它所在的树的根的路径上的所有的节点的权增加一个数

5.查询从某个节点到它所在的树的根的路径上的所有的节点的权的最小值

6.把一棵树从某个节点和它的父亲处断开，使其成为两棵树

7.让一棵树的根成为另一棵树的某个节点的儿子，从而合并这两棵树

8.把某棵树的根修改为它的某个节点

9.查询在同一棵树上的两个节点的LCA

*10.修改以某个节点为根的子树的所有节点的权

*11.查询以某个节点为根的子树的所有节点的权的最小值

......

为了简化问题，我们只考虑一个简化版本：不支持10和11操作

百度文库里有关于动态树的论文。其中介绍的比较多的是Link-Cut Tree，它的核心思想是：

把树剖分成若干个链，之后用平衡树去维护维护这些链。

可以选择的平衡树有Splay，或者在树的形态不改变的情况下使用“全局平衡二叉树”（见2007年某人的某论文）。

有了动态树，我们能够做很多事情，例如：

优化网络流（看某些有关费用流的论文吧）

除了这个“正当”用途外，还有各种“不正当用途”：

并查集（不光支持合并，还支持按某种规则分离呢）

LCA（动态的LCA啊）

RMQ（所谓数列就是一个链，所谓链就是一种退化了的树。对每次要操作的区间，先从树上砍下来，操作完之后合并回去）

可并优先队列（所谓队列就是一个链。。。。。。）

如果你不嫌弃常数，如果你有套模板刷题的习惯，那么可以“一切皆动态树”。

代码真的不算很长，也就190行，3.9K（不算很长。。。）

http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree.cpp

就是这个：

#include <cstdio>
#include <algorithm>
#define NMax 10000
using namespace std;
struct node{
int key,mn,delta;
int revmark;
    node *p,*l,*r;
    node(){}
};
struct DynamicTree{
    node *nodes;
int N;
static void ini_node(node *p){
        p->p=p->l=p->r=NULL;
        p->revmark=0;p->delta=0;p->mn=~0u>>2;p->key=~0u>>2;
    }
static int isroot(node *p){return !p->p || (p->p->l!=p && p->p->r!=p);}
    DynamicTree(int n){
        N=n;
        nodes=new node[n];
for (int i=0;i<n;i++)ini_node(nodes+i);
    }
static void inc(node *p,int d){
        p->key+=d;p->mn+=d;p->delta+=d;
    }
static void rev(node *p){
        swap(p->l,p->r);
        p->revmark^=1;
    }
static void down(node *p){
if (p->delta){
if (p->l)inc(p->l,p->delta);
if (p->r)inc(p->r,p->delta);
            p->delta=0;
        }
if (p->revmark){
if (p->l)rev(p->l);
if (p->r)rev(p->r);
            p->revmark=0;
        }
    }
static void update(node *p){
        p->mn=p->key;
if (p->l && p->l->mn+p->delta<p->mn)p->mn=p->l->mn+p->delta;
if (p->r && p->r->mn+p->delta<p->mn)p->mn=p->r->mn+p->delta;
    }
static void zig(node *p){
        node *x=p->p,*y=x->p;
        p->p=y;x->p=p;
if (y){
if (x==y->l)y->l=p;
else if (x==y->r)y->r=p;
        }
        x->l=p->r;if (x->l)x->l->p=x;
        p->r=x;
        update(x);
        update(p);
    }
static void zag(node *p){
        node *x=p->p,*y=x->p;
        p->p=y;x->p=p;
if (y){
if (x==y->l)y->l=p;
else if (x==y->r)y->r=p;
        }
        x->r=p->l;if (x->r)x->r->p=x;
        p->l=x;
        update(x);
        update(p);
    }
static void Splay(node *p){
static node *stack[NMax];
int top=1;
        stack[0]=p;
for (node *q=p;!isroot(q);)stack[top++]=(q=q->p);
while (top)down(stack[--top]);
while (!isroot(p)){
            node *q=p->p;
if (isroot(q)){
if (q->l==p)zig(p);
else zag(p);
            }else{
if (q==q->p->l){
if (p==q->l){
                        zig(q);zig(p);
                    }else{
                        zag(p);zig(p);
                    }
                }else{
if (p==q->r){
                        zag(q);zag(p);
                    }else{
                        zig(p);zag(p);
                    }
                }
            }
        }
    }
static node* head(node *p){
for (down(p);p->l;p=p->l)down(p);
        Splay(p);
return p;
    }
static node *tail(node *p){
for (down(p);p->r;p=p->r)down(p);
        Splay(p);
return p;
    }
static node *prev(node *p){
        Splay(p);
if (!p->l)return NULL;
        node *q=p->l;
for (;q->r;q=q->r)down(q);
        Splay(q);
return q;
    }
static node *next(node *p){
        Splay(p);
if (!p->r)return NULL;
        node *q=p->r;
for (;q->l;q=q->l)down(q);
        Splay(q);
return q;
    }
static node *Expose(node *p){
        node *q;
for (q=NULL;p;p=p->p){
            Splay(p);
            p->r=q;
            update(q=p);
        }
return q;
    }
    node *getNode(int id){return id>=0&&id<N?nodes+id:NULL;}
int getId(node *p){return p?p-nodes:-1;}
static int AskMin(node *p){
return Expose(p)->mn;
    }
int AskMin(int id){return AskMin(getNode(id));}
static void Increase(node *p,int d){
        inc(Expose(p),d);
    }
void Increase(int id,int d){Increase(getNode(id),d);}
static void Change(node *p,int a){
        Splay(p);
        p->key=a;
        update(p);
    }
void Change(int id,int a){Change(getNode(id),a);}
static void ChangeRoot(node *p){
        rev(Expose(p));
    }
void ChangeRoot(int id){ChangeRoot(getNode(id));}
static node *getParent(node *p){
        Splay(p);
if (p->l)return prev(p);
return p->p;
    }
int getParent(int id){return getId(getParent(getNode(id)));}
static node *getRoot(node *p){
return head(Expose(p));
    }
int getRoot(int id){return getId(getRoot(getNode(id)));}
static void Merge(node *p,node *q){
        Splay(q);
        q->p=p;
    }
void Merge(int p,int q){Merge(getNode(p),getNode(q));}
static void Cut(node *p){
        Splay(p);
if (p->l){
            p->l->p=p->p;
            p->p=p->l=NULL;
        }else p->p=NULL;
    }
void Cut(int id){Cut(getNode(id));}
static node *LCA(node *p,node *q){
        node *x=head(Expose(p));
        node *y=Expose(q),*z=head(y);
if (x==z)return y;
return NULL;
    }
int LCA(int p,int q){return getId(LCA(getNode(p),getNode(q)));}
};
int main()
{
return 0;
}