【整理】算法竞赛数据结构学习笔记

区间信息维护

前缀和与差分

多维前缀和

多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。
例如二维前缀和求法:

  1. $sum_{i,j}=a_{i,j}$
  2. $sum_{i,j}+=sum_{i-1,j}$
  3. $sum_{i,j}+=sum_{i,j-1}$

例题:NC225630 智乃酱的子集与超集

数列上加多项式

给一个数列的一部分连续的数分别加上 $f(1),f(2),\dots,f(n),\dots$
key:任何一个最高次数为 $n$ 的多项式连续数列可以通过差分 $n+1$ 次表示。
因此,对于区间 $(l,r)$,我们先差分出一个从 $l$ 开始的 $f(1)$ 开始的数列,再差分出一个从 $r+1$ 开始的 $-f(r-l+2)$ 开始的数列抵消影响。
例题:NC225628 智乃酱的静态数组维护问题多项式

树状数组与线段树

离线后树状数组

一些统计种类的问题可以通过这个方法来解决。
例如 [HEOI2012]采花

LazyTag

懒标记是线段树的核心之一。考虑需要维护的数值在懒标记下的运算很关键。
给出例题:
线段树
智乃酱的cube

带修改的 DP(DDP)

通过线段树可以完成一些能通过矩阵优化的 DP 的待修改版本。
智乃酱的双塔问题·极(带修改的DP,DDP)
智乃酱的双塔问题·改

势能线段树(带暴力成分的线段树)

有些数据具有单调性,就像势能不断下降至 0 势能点,观察并维护之可以让一些线段树结构看似有暴力修改,实则复杂度合法。
势能线段树模板题二
弩蚊怒夏

李超线段树

李超线段树是用来维护平面上的若干点的,用于快速找出在某一个 x 坐标,那一条的 y 值最大或最小。这在动态规划优化中也有作用。
模板:智乃的直线

平衡树

绝大部分时候,set 都可以解决问题,因此在比赛中非必要,不要贸然使用平衡树,平衡树在 ACM/ICPC 中并不是一个需要经常手写的数据结构。由于相较于 Treap,Splay 拥有更广泛的使用场合,因此此处只呈现 Splay 的代码。

[!Warning]set 中每个元素只能出现一次,遇到有重复数据的情况是不能使用的,需要使用 multiset

平衡树管理数组的一个优势是他的区间长度是自由的,因此对于区间反转这一问题,线段树无法通过打 tag 来解决,而平衡树可以做到,这一类需要严格对某一个自由长度区间打 tag 的操作是平衡树之于线段树的优势。

我的博客中有对平衡树的详细学习笔记

例题:

[HNOI2004]宠物收养所 请注意,本题可以通过 Set 解决,相较于手写平衡树,这是更优秀的选择。

普通平衡树 这是一道模板题

文艺平衡树 这是另一道模板题

跳表

首先,跳表是一种离线算法, 这是很重要的一点。

跳表(ST 表)有两种,一种是传统的 log 型跳表,建立复杂度为 $O(n\log n)$,但必须要满足所求的内容在区间重叠不影响结果(例如,gcd 或者 max/min)。

另一种是根号型跳表,记 $f_{i,j}$ 为从 $i$ 开始的 $j$ 个数的值(例如,和),记 $g_{i,j}$ 为从 $i$ 开始的 $block \times j$ 个数的和,通常我们令 $block=\operatorname{sqrt}(n)$。这样,我们可以在 $O(n \sqrt n)$ 的时间复杂度内建立跳表,然后在 $O(1)$ 的时间复杂度内进行单次查询(大块+小块)。请注意,只有当查询次数不小于数组总长的 $100$ 倍时才需要使用根号跳表,否则,线段树是一个更好的选择。不同于 log 型跳表,区间跳表只要满足区间可加性就能做(这与线段树的要求相同,不是吗)。

分块

对于一些问题,我们可以将整个区间分成 $\operatorname{sqrt}(n)$ 个块。如果我们可以记录每个块的总值,或是对无效的块打上标记,我们就可以保证每次查询的时间复杂度为 $O(\sqrt n)$。

莫队

普通莫队

普通莫队是一个离线算法。

我们先将整个区间分成 $\sqrt n$ 个块。对于所有查询 $[l,r]$,我们先根据 $l$ 所在的块进行升序排序,相同时再根据 $r$ 的大小进行升序排序。我们以这个顺序处理所有查询,对于一次查询,我们只需要访问上一次查询没有查询过的点,再删除该次查询没有但上一次查询有的点即可。时间复杂度为 $O(n\sqrt n)$。

例题:小Z的袜子

带修莫队

在普通莫队的前提下,如果题目有了单点修改的操作,我们就可以使用带修莫队。

待修莫队给了所有查询第三维时间戳,即代表这个查询经过了几次单点修改。对于所有查询 $[l,r,tim]$,我们先根据 $l$ 所在的块进行升序排序,相同时再根据 $r$ 所在的块进行升序排序,仍然相同则根据 $tim$ 的大小升序排序。请注意,再待修莫队中,块长为 $n^{\frac{2}{3}}$。最终时间复杂度为 $O(n^{\frac{3}{5}})$.

例题:数颜色

树上莫队

如果有一个问题和普通莫队要求的内容类似,但是查询的是树上一条链的结果,就可以用树上莫队。

首先,我们求出这棵树的欧拉序(即,一个点进出分别会被继续一次,记进的时间戳为 $in_u$,出的时间戳为 $out_u$)。对于一次询问 $[u,v]$,不妨令 $in_u \le in_v$,如果 $out_u \ge out_v$,即点 $v$ 是点 $u$ 子树上的点,则 $(u,v)$ 链上的点是欧拉序中 $[in_u,in_v]$ 区间内所有出现次数为奇数的点,否则 $(u,v)$ 链上的点是欧拉序中 $[out_u,in_v]$ 区间内所有出现次数为奇数的点,再加上 $\operatorname{lca}(u,v)$。如此以来,我们就把树上的问题转化成了区间查询,再利用普通莫队的方法即可,只是对数的加减改成了对某点出现次数奇偶性的更改,若为奇数,则加入该点,否则删除该点。令块长为 $\sqrt n$,则时间复杂度为 $O(n\sqrt n)$​。

例题:树上莫队模板题

可并堆/左偏树

左偏树是一种堆的实现,他保证了对于任意一点,左链的长度始终大于右链,因此在合并过程中,只要我们一直考虑右链,即,若要合并的两个小根堆堆顶为 $x,y$,若 $x<y$ 就用 $x$ 的右儿子与 $y$ 继续合并,反之用 $y$ 的右儿子和 $x$ 继续合并,如此一来,就能保证合并的时间复杂度为 $O(\log n)$​。

例题:【模板】左偏树/可并堆

笛卡尔树

笛卡尔树是一种中序遍历与数列相同,且具有堆结构的一种二叉树,可以把数列问题转化到树上问题。我们可以用一个单调栈来建立笛卡尔树,例如,对于一个大根堆的笛卡尔树,可以通过如下代码建立:

stack<int> st;
for(int i=1;i<=n;i++){
    while(!st.empty()&&a[i]>a[st.top()]){ls[i]=st.top();st.pop();}
    if(!st.empty()) rs[st.top()]=i;
    st.push(i);
}

例题:Add One 2

代码

树状数组

#define lowbit(x) ((x)&(-x))
ll tr[N];
void add(int x,ll k){while(x<=n){tr[x]+=k;x+=lowbit(x);}}
ll query(int x){ll ret=0;while(x){ret+=tr[x];x-=lowbit(x);}return ret;}

线段树

struct SegmentTree{
    #define ls ((u)<<1)
    #define rs ((u)<<1|1)
    struct node{

        int l,r;
    }tr[4*N];
    void init_lazy(int u){

    }
    void union_lazy(int fa,int u){

    }
    void cal_lazy(int u){

    }
    void pushdown(int u){
        if(){
            cal_lazy(u);
            if(tr[u].l!=tr[u].r){
                union_lazy(u,ls);
                union_lazy(u,rs);
            }
            init_lazy(u);
        }
    }
    void pushup(int u){
        pushdown(ls);pushdown(rs);

    }
    void build(int u,int l,int r,ll *A){
        tr[u].l=l;tr[u].r=r;
        init_lazy(u);
        if(l==r){

        }
        else{
            int mid=(l+r)>>1;
            build(ls,l,mid,A);build(rs,mid+1,r,A);
            pushup(u);
        }
    }
    void change(int u,int L,int R,ll k,int opt){
        pushdown(u);
        if(tr[u].r<=R&&tr[u].l>=L){
            tr[u].lazy[opt]=k;
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid){change(ls,L,R,k,opt);}
        else if(L>mid){change(rs,L,R,k,opt);}
        else{change(ls,L,R,k,opt);change(rs,L,R,k,opt);}
        pushup(u);
    }
    ll query(int u,int L,int R){
        pushdown(u);
        if(tr[u].r<=R&&tr[u].l>=L) return ;
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid) return query(ls,L,R);
        else if(L>mid) return query(rs,L,R);
        else return query(ls,L,R)+query(rs,L,R);
    }
}ST;

李超线段树

struct Line{
    ll k,b;
    ll val(ll x){return k*x+b;}
    Line(ll kk=0,ll bb=0){
        k=kk;b=bb;
    }
};
struct Lichao_SegmentTree{
    const ll LCinf=1e18;
    #define ls ((u)<<1)
    #define rs ((u)<<1|1)
    ll crossX(Line i,Line j){
        return (j.b-i.b)/(i.k-j.k);
    }
    struct node{
        Line lin;
        int l,r;
        bool has_lin,vis;
    }tr[4*N];
    void build(int u,int l,int r){
        tr[u].l=l;tr[u].r=r;
        tr[u].vis=tr[u].has_lin=0;
        if(l==r){
            return;
        }
        else{
            int mid=(l+r)>>1;
            build(ls,l,mid);build(rs,mid+1,r);
        }
    }
    void insert(int u,int L,int R,Line x){
        if(tr[u].l==0&&tr[u].r==0) return;
        if(tr[u].r<=R&&tr[u].l>=L){
            if(!tr[u].has_lin){
                tr[u].has_lin=1;
                tr[u].lin=x;
                return;
            }
            if(tr[u].lin.val(tr[u].l)>=x.val(tr[u].l)&&tr[u].lin.val(tr[u].r)>=x.val(tr[u].r)) return;
            if(tr[u].lin.val(tr[u].l)<=x.val(tr[u].l)&&tr[u].lin.val(tr[u].r)<=x.val(tr[u].r)){tr[u].lin=x;return;}
            int mid=(tr[u].l+tr[u].r)/2;
            if(crossX(tr[u].lin,x)<=mid){
                if(x.k<tr[u].lin.k) insert(ls,L,R,x);
                else{insert(ls,L,R,tr[u].lin);tr[u].lin=x;}
            }
            else{
                if(x.k>tr[u].lin.k) insert(rs,L,R,x);
                else{insert(rs,L,R,tr[u].lin);tr[u].lin=x;}
            }
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid){insert(ls,L,R,x);}
        else if(L>mid){insert(rs,L,R,x);}
        else{insert(ls,L,R,x);insert(rs,L,R,x);}
    }
    ll query(int u,int x){
        if(!tr[u].has_lin) return -LCinf;
        if(tr[u].l==tr[u].r) return tr[u].lin.val(x);
        int mid=(tr[u].l+tr[u].r)/2;
        if(x<=mid) return max(tr[u].lin.val(x),query(ls,x));
        else return max(tr[u].lin.val(x),query(rs,x));
    }
}ST;

Splay

struct SplayTree{
    struct Splay_Tree{
        int son[2],fa,cnt,val,siz,tag;
    }tree[N];
    int root,cnt;
    const int inf=2147483647;
    void pushup(int u){
        tree[u].siz=tree[tree[u].son[0]].siz+tree[tree[u].son[1]].siz+tree[u].cnt;
    }
    void pushdown(int x){
        if(tree[x].tag){

        }
    }
    int build(int l,int r,int fa){//根据数组 a 建树并返回根结点,如果不需要建树,请删除这一段代码
        if(l>r) return 0;
        int v=++cnt;
        tree[v].fa=fa;
        tree[v].cnt=1;
        int mid=(l+r)>>1;
        //tree[v].val=a[mid];
        tree[v].son[0]=build(l,mid-1,v);
        tree[v].son[1]=build(mid+1,r,v);
        pushup(v);
        return v;
    }
    bool check(int u){
        return tree[tree[u].fa].son[1]==u;
    }
    void rotate(int u){//单次旋转操作
        int fa=tree[u].fa;
        int ffa=tree[fa].fa;
        pushdown(fa);pushdown(u);
        int k=check(u);
        tree[ffa].son[check(fa)]=u;tree[u].fa=ffa;
        tree[fa].son[k]=tree[u].son[k^1];tree[tree[u].son[k^1]].fa=fa;
        tree[u].son[k^1]=fa;tree[fa].fa=u;
        pushup(fa);pushup(u);
    }
    void splay(int u,int goal){//将 u 向上旋转直至父亲为 goal(goal=0->旋到根)
        while(tree[u].fa!=goal){
            int fa=tree[u].fa;
            int ffa=tree[fa].fa;
            pushdown(fa);pushdown(u);
            if(ffa!=goal){
                if(check(u)==check(fa)) rotate(fa);
                else rotate(u);
            }
            rotate(u);
        }
        if(!goal) root=u;
    }
    void insert(int x){//插入一个数
        int u=root,fa=0;
        while(tree[u].val!=x&&u){
            pushdown(u);
            fa=u;
            u=tree[u].son[x>tree[u].val];
        }
        if(u) tree[u].cnt++;
        else{
            u=++cnt;
            if(fa) tree[fa].son[x>tree[fa].val]=u;
            tree[u].fa=fa;tree[u].val=x;
            tree[u].cnt=tree[u].siz=1;
        }
        splay(u,0);
    }
    void find(int x){//寻找一个数
        int u=root;
        while(x!=tree[u].val&&tree[u].son[x>tree[u].val]){
            pushdown(u);
            u=tree[u].son[x>tree[u].val];
        }
        splay(u,0);
    }
    void del(int x){//删除一个数
        int l=frne(x,0);
        int r=frne(x,1);
        splay(l,0);splay(r,l);
        int tmp=tree[r].son[0];
        if(tree[tmp].cnt>1){
            tree[tmp].cnt--;
            splay(tmp,0);
        }
        else tree[r].son[0]=0;
    }
    int query(int rk){//查找排名为 rk 的数
        int u=root;
        pushdown(u);
        while(1){
            if(tree[tree[u].son[0]].siz>=rk){
                u=tree[u].son[0];
            }
            else if(tree[tree[u].son[0]].siz+tree[u].cnt>=rk) return u;
            else{
                rk-=tree[tree[u].son[0]].siz+tree[u].cnt;
                u=tree[u].son[1];
            }
            pushdown(u);
        }
    }
    int frne(int x,int opt){//求 x 的前驱/后继
        find(x);
        int u=root;
        if((!opt&&tree[u].val<x)||(opt&&tree[u].val>x)) return u;
        pushdown(u);
        u=tree[u].son[opt];
        while(tree[u].son[opt^1]){
            pushdown(u);
            u=tree[u].son[opt^1];
        }
        return u;
    }
}Splay;
//建议在操作开始前使用这两行代码来减少特判
//Splay.insert(-inf);Splay.insert(inf);

普通莫队

struct node{
    int l,r,id,ans;
}q[N];
bool cmp1(node i,node j){
    if(i.l/block==j.l/block) return i.r<j.r;
    else return i.l/block<j.l/block;
}
bool cmp2(node i,node j){
    return i.id<j.id;
}
void add(int k){
    //do something
}
void del(int k){
    //do something
}
void solve(){
    scanf("%d%d",&n,&m);block=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r) add(++r);
        while(r>q[i].r) del(r--);
        while(l<q[i].l) del(l++);
        while(l>q[i].l) add(--l);
        //do something
    }
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;i++){
        printf("%d\n",q[i].ans);
    }
}

带修莫队

int cntq,cntr,block;
char op[5];
struct node{
    int l,r,tim,id,ans;
}q[N];
struct node2{
    int pos,col;
}R[N];
bool cmp(node i,node j){
    if(i.l/block!=j.l/block) return i.l/block<j.l/block;
    if(i.r/block!=j.r/block) return i.r/block<j.r/block;
    return i.tim<j.tim;
}
bool cmp2(node i,node j){
    return i.id<j.id;
}
void add(int k){
    //do something
}
void del(int k){
    //do something
}
void solve(){
    scanf("%d%d",&n,&m);block=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='Q'){
            cntq++;
            scanf("%d%d",&q[cntq].l,&q[cntq].r);
            q[cntq].id=cntq;q[cntq].tim=cntr;
        }
        else{
            cntr++;
            scanf("%d%d",&R[cntr].pos,&R[cntr].col);
        }
    }
    sort(q+1,q+1+cntq,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=cntq;i++){
        while(r<q[i].r) add(++r);
        while(r>q[i].r) del(r--);
        while(l<q[i].l) del(l++);
        while(l>q[i].l) add(--l);
        while(t<q[i].tim){
            t++;
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) del(R[t].pos);
            swap(a[R[t].pos],R[t].col);
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) add(R[t].pos);
        }
        while(t>q[i].tim){
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) del(R[t].pos);
            swap(a[R[t].pos],R[t].col);
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) add(R[t].pos);
            t--;
        }
        q[i].ans=now;
    }
    sort(q+1,q+1+cntq,cmp2);
    for(int i=1;i<=cntq;i++){
        printf("%d\n",q[i].ans);
    }
}

树上莫队

struct node{
    int to,nxt;
}e[M];
int block,head[N],cnt,n,m,col[N];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int euler[N],in[N],out[N],cnte;
int fa[N][20],dep[N];
void dfs(int u,int f){
    euler[++cnte]=u;in[u]=cnte;
    fa[u][0]=f;dep[u]=dep[f]+1;
    for(int i=1;i<=19;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f) continue;
        dfs(v,u);
    }
    euler[++cnte]=u;out[u]=cnte;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}
struct nodeModui{
    int l,r,id,ans,ex;
}q[N];
bool cmp1(nodeModui i,nodeModui j){
    if(i.l/block==j.l/block) return i.r<j.r;
    else return i.l/block<j.l/block;
}
bool cmp2(nodeModui i,nodeModui j){
    return i.id<j.id;
}
bool tag[N];
int tot[COL],now;
void work(int u){
    tag[u]^=1;
    if(tag[u]==1){
        //do something
    }
    else{
        //do something
    }
}
void MoDui(){
    sort(q+1,q+1+m,cmp1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r) work(euler[++r]);
        while(r>q[i].r) work(euler[r--]);
        while(l<q[i].l) work(euler[l++]);
        while(l>q[i].l) work(euler[--l]);
        if(q[i].ex){
            work(q[i].ex);
            q[i].ans=now;
            work(q[i].ex);
        }
        else{
            q[i].ans=now;
        }
    }
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,1);block=sqrt(2*n);
    scanf("%d",&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        if(in[u]>in[v]) swap(u,v);
        if(out[u]>=out[v]){
            q[i].l=in[u];
            q[i].r=in[v];
            q[i].ex=0;
        }
        else{
            q[i].l=out[u];
            q[i].r=in[v];
            q[i].ex=lca(u,v);
        }
        q[i].id=i;
    }
    MoDui();
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;i++){
        printf("%d\n",q[i].ans);
    }
}

左偏树/可并堆

int fa[N],dis[N],ls[N],rs[N];
int find(int x){
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
struct node{
    int id,val;
}a[N];
bool operator <(node i,node j){
    return i.val==j.val?i.id<j.id:i.val<j.val;
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(a[y]<a[x]) swap(x,y);
    rs[x]=merge(rs[x],y);
    if(dis[rs[x]]>dis[ls[x]]) swap(rs[x],ls[x]);
    dis[x]=dis[rs[x]]+1;
    return x;
}

树上信息维护

树的 dfs 序

在二叉树中我们有前序,中序,后续。而对于一棵普通树,我们有三种常用的 dfs 序。

  • dfs 序:第一次遍历一个点时把该点加入序列(上图的一个可能的 dfs 序为 1,4,2,5,7,6,3)。
    • dfs 序通常用于子树和树链操作类问题。
  • 扩展 dfs 序:第一次遍历一个点时,以及遍历一个点的儿子前,把该点加入序列(上图的一个可能的扩展 dfs 序为 1,1,4,1,2,2,5,5,7,2,6,1,3)。
    • 对于两个点 $u,v$,其 LCA 就是 $[id_u,id_v]$ 区间中深度最低的点,容易发现这样的点一定是唯一的。可以通过维护一个 pair<depth,id> 来做到 $O(1)$ 查询 LCA。
    • 通过扩展 dfs 序,我们可以把 LCA 问题转化为 RMQ 问题;通过笛卡尔树,我们可以把 RMQ 问题转化为 LCA 问题,这有时候有益于思考与解决。
  • 欧拉序:在第一次遍历一个点和这个点遍历完成后,把该点加入序列(上图的一个可能的欧拉序为 1,4,4,2,5,7,7,5,6,6,2,3,3,1)。
    • 欧拉序通常用于抵消前后的影响,例如树链上莫队,树链上亦或和。
    • 也可以利用欧拉序列维护信息,例如ETT(欧拉环游树)。

注意,不论在哪一种序列,$id_x$ 都表示点 $x$ 第一次进入序列对应的时间戳($dfn$)。

树上差分与树上倍增

树上差分与一维差分类似。对于树链上的差分,通常在点 $u,v,lca(u,v),fa_{lca(u,v)}$ 四点处打 tag。

树上倍增的思想即倍增求 lca 的影响,不多赘述。

例题:[JLOI2014]松鼠的新家

树链剖分/轻重链剖分

我的树链剖分学习笔记

树链剖分的核心思想就是将树分解成若干条链,同一条的 dfs 序是连续的,并保证一个点可以经过不超过 $\log n$ 条不同的链到达树根。在轻重链剖分中,我们通过优先走重儿子(子树大小最大的儿子)来做到这一点。

完成链分解后,我们可以利用一些数据结构来维护。对于子树的操作,其等价于对一段 dfs 序连续的点进行操作;对于链的操作,其等价于对 $\log n$ 段 dfs 序连续的点进行操作。

例题:

树上路径

[HAOI2015]树上操作

[LNOI2014]LCA

代码

树链剖分

int dep[N],son[N],siz[N],fa[N];
void dfs1(int u,int Fa){
    dep[u]=dep[Fa]+1;siz[u]=1;fa[u]=Fa;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==Fa) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
    }
}
int top[N],dfn,id[N],idx[N];
void dfs2(int u,int Top){
    top[u]=Top;id[u]=++dfn;idx[dfn]=u;
    if(son[u]) dfs2(son[u],Top);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        //do something
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇