对于某些对子树的统计问题,我们固然可以用DSU on Tree来解决,但是一旦带上修改,甚至是加上历史化版本的查询,我们就不得不求助于其他的算法,本篇将对线段树合并进行讲解

---

线段树合并一般用于对子树的统计,一般的套路就是对树的每一个节点都开上一颗动态开点线段树,然后统计子树信息时,合并所有儿子信息,统计答案,然后继续向上走;

例题也很多,比如[USACO17JAN]Promotion Counting晋升者计数,【NOIP2016 DAY1】天天爱跑步等等都可以这样乱搞,实现起来也非常好理解,这是针对天天爱跑步类型(权值线段树)的\(Merge\)代码:

\(code\):

void merge(int &x,int y){    if(!x||!y){x=x+y;return;}    sum[x]+=sum[y];    merge(ls[x],ls[y]);    merge(rs[x],rs[y]);}

如果希望改为维护历史版本,可以这样改:

int merge(int x,int y){    if(!x||!y){ return x+y;return;}    int p=++tot;       ls[p]=merge(ls[x],ls[y]);    rs[p]=merge(rs[x],rs[y]);        sum[p]=sum[ls[p]]+sum[rs[p]]    return p;}

这里是晋升者计数的\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;char buf[1<<20],*p1,*p2;inline char gc(){//    return getchar();    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;}template
         
          inline void read(T &x){ char tt; bool flag=0; while(!isdigit(tt=gc())&&tt!='-'); tt=='-'?(flag=1,x=0):(x=tt-'0'); while(isdigit(tt=gc())) x=x*10+tt-'0'; if(flag) x=-x;}const int maxn=1000002;int n,tot;int w[maxn],hashh[maxn];int root[maxn<<2],sum[maxn<<2],ls[maxn<<2],rs[maxn<<2];int ans[maxn];vector
          
           G[maxn];void modify(int &p,int l,int r,int x,int d){ if(!p) p=++tot; if(l==r) {sum[p]+=d;return;} int mid=l+r>>1; if(mid>=x) modify(ls[p],l,mid,x,d); if(mid
           
            =x&&y>=r) return sum[p]; int mid=l+r>>1; int tmp=0; if(x<=mid) tmp+=query(ls[p],l,mid,x,y); if(y>mid) tmp+=query(rs[p],mid+1,r,x,y); return tmp;}void dfs(int x){ modify(root[x],1,n+1,w[x],1); for(int i=G[x].size()-1;i>=0;i--) { int p=G[x][i]; dfs(p); merge(root[x],root[p]); } ans[x]=query(root[x],1,n+1,w[x]+1,n+1);}int main(){ read(n); for(int i=1;i<=n;i++) read(w[i]),hashh[i]=w[i]; sort(hashh+1,hashh+1+n); for(int i=1;i<=n;i++) w[i]=lower_bound(hashh+1,hashh+1+n,w[i])-hashh; for(int i=2;i<=n;i++) { int x; read(x); G[x].push_back(i); } dfs(1);// for(int i=1;i<=n;i++)// printf("%d ",query(root[1],1,n,i,i)); for(int i=1;i<=n;i++) printf("%d\n",ans[i]);}
           
          
         
        
       
      
     
    

简单好写,易于理解