线段树合并&分裂

线段树合并

• 数据结构
• 最近公共祖先
• 倍增
• 线段树

P4556 Vani有约会 雨天的尾巴 /【模板】线段树合并

整体思路

• 连边
• 倍增（求LCA）（存深度）
• 存救济粮发放信息（打懒标记）
• 遍历基础信息
• 动态开点
• 合并线段树
• 记录结果
• 输出

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
}
const int o_o=1e5+10;
int n,m;
struct pp{
  int v;
  int n_t;
}p_p[o_o<<1];//存边 
int h_d[o_o],x_p;
int f_a[o_o][31];//存父节点（倍增） 
int d_p[o_o];//存点的深度 
int a_s[o_o];//存储答案 
struct po{
    int i_d,n_m;
    bool operator <(const po &a)const{//这里必须是小于号，max 默认的判断小于。
    return (n_m==a.n_m)?i_d>a.i_d:n_m<a.n_m;//如果数量一样，返回标号小的 
  }
    po operator +(const po &a)const{
    return (po){i_d,n_m+a.n_m};//数量累计 
  }
}t_r[40*o_o];
vector<po>l_n[o_o];//线段树懒标记 
void a_d(int u,int v){//建边 
  p_p[++x_p].v=v;
  p_p[x_p].n_t=h_d[u];
  h_d[u]=x_p;
}
int s[40*o_o][2];//节点左右儿子 
int s_m;//节点赋新编号 
void g_a(int p,int l,int r,po k){//动态开点 
    if(r-l==1){//是叶子  
    t_r[p]=k+t_r[p];//合并，注意这里的加法顺序不能颠倒 
    //不能写成 t_r[p]+k，由于重载运算符，我们取的是前者的 id（救济粮编号） 
    return;
  }
  int m_i=(l+r)>>1;
    if(k.i_d<=m_i){
      s[p][0]=s[p][0]?s[p][0]:++s_m;//左儿子已有编号，继续用；没有编号，赋新编号 
    g_a(s[p][0],l,m_i,k);//继续遍历 
  }else {
      s[p][1]=s[p][1]?s[p][1]:++s_m;//右儿子已有编号，继续用；没有编号，赋新编号 
      g_a(s[p][1],m_i,r,k);//继续遍历 
  }
  t_r[p]=max(t_r[s[p][0]],t_r[s[p][1]]);//求左右儿子最大值（同时更新了编号） 
}
void b_g(int a,int b,int l,int r){
    if(r-l==1){//是叶子
    t_r[a]=t_r[a]+t_r[b];//合并 
    return;
  }
  int m_i=(l+r)>>1;
  
  //将 b 并到 a 中 
    if(s[a][0]&&s[b][0])b_g(s[a][0],s[b][0],l,m_i);//左儿子都存在，开始合并 
  else if(s[b][0])s[a][0]=s[b][0];//a 没有左儿子 
  //b 若没有儿子不用操作
   
    if(s[a][1]&&s[b][1])b_g(s[a][1],s[b][1],m_i,r);//右儿子都存在，开始合并 
  else if(s[b][1])s[a][1]=s[b][1];//a 没有右儿子 
  //b 若没有儿子不用操作
  
  t_r[a]=max(t_r[s[a][0]],t_r[s[a][1]]);//存储最大值（同时更新了编号） 
}
void d_1(int k){//倍增求 LCA 
    for(int i=0;f_a[k][i];i++)f_a[k][i+1]=f_a[f_a[k][i]][i];
  d_p[k]=d_p[f_a[k][0]]+1;//处理深度 
    for(int i=h_d[k];i;i=p_p[i].n_t)
    if(p_p[i].v!=f_a[k][0]){
      f_a[p_p[i].v][0]=k;
      d_1(p_p[i].v);//继续遍历 
    }
}
int l_a(int u,int v){//找公共祖先 
    if(d_p[u]<d_p[v])swap(u,v);
  for(int d=d_p[u]-d_p[v],i=0;d;d>>=1,i++)//两者深度相同 
    if(d&1)u=f_a[u][i];//二进制判断（将差的值分解成二进制判断） 
    if(u==v)return u;
  for(int i=18;i>=0;i--){//跳公共祖先 
    if(f_a[u][i]!=f_a[v][i]){
      u=f_a[u][i];
      v=f_a[v][i];
    }
  }
    return f_a[u][0];//返回公共祖先 
}
void d_2(int k){//合并线段树 
    for(int i=h_d[k];i;i=p_p[i].n_t)
    if(p_p[i].v!=f_a[k][0]){
      d_2(p_p[i].v);//按顺序合并线段树（类似于拓扑序的合并，不会因为合并的顺序互相影响结果） 
      b_g(k,p_p[i].v,0,1e5);//合并线段树 
    }
    for(vector<po>::iterator it=l_n[k].begin();it!=l_n[k].end();++it)
    g_a(k,0,1e5,*it);//释放懒标记 
    a_s[k]=t_r[k].i_d;//存储结果 
}
int main(){
    n=r_r();
    m=r_r();
  s_m=n;
    for(int i=1,u,v;i<n;i++){//连边，建图 
    u=r_r();
    v=r_r();
    a_d(u,v);
    a_d(v,u);
  }
  d_1(1);//处理 LCA 
    for(int i=1,u,v,z;i<=m;i++){
        u=r_r();
        v=r_r();
        z=r_r();//读入救济粮发放 
    int g_f=l_a(u,v);//获取两者公共祖先 
        l_n[u].push_back((po){z,1});//在叶节点打标记（前缀和求法） 
    l_n[v].push_back((po){z,1});//打标记 
        l_n[g_f].push_back((po){z,-1});//标记结束（这个点还有 1 的权值，所以要保留 1 的值） 
    l_n[f_a[g_f][0]].push_back((po){z,-1});//标记彻底结束 
    }
  d_2(1);//线段树合并 
  for(int i=1;i<=n;i++)printf("%d\n",a_s[i]);//输出结果 
  return 0;
}

线段树分裂

• 数据结构
• 平衡树
• 线段树

P5494 【模板】线段树分裂

整体思路

• 实现动态开点
• 建树（根节点为 1）
• 实现操作一：分裂（开点）
• 实现操作二：合并（合并，删点）
• 实现废点回收（再利用）
• 实现操作三：插入（叶子结点加权）
• 实现操作四：查找区间数的个数（线段树区间和）
• 实现操作五：根据排名找原数（Splay）

各变量意义

const int o_o=6e5+10;//数组大小 
int n,m;//序列长度，操作次数 
struct po{
  int l,r;//线段树节点左右边界 
  long long s_m;//区间和 
}t_r[o_o<<2];
int x_p=0;//所有节点个个数（包括垃圾桶中的点） 
int s_m=0;//垃圾桶中可用的点 
int r_s[o_o<<2];//节点垃圾桶 
int r_t[o_o];//记录每个序列的线段树根节点 
int x_t=1;//新可重集序号 
int a_a[o_o];//原序列 

实现动态开点&废点回收（再利用）

动态开点用来即时给新节点赋予编号。由于本题空间范围较紧迫，要进行废点的回收利用。

我们要再开一个数组专门用废弃的点，要新时的时，先不开新点，先废物利用。（新开一个记录废点的数组要比直接开两个存点数组优的多）。

void d_l(int &k){//删除节点 
  t_r[k].l=t_r[k].r=t_r[k].s_m=0;//清空数据 
  r_s[++s_m]=k;//放入垃圾桶 
  k=0;//节点编号清空 
}
int n_w(){//赋新节点编号 
  if(s_m)return r_s[s_m--];//垃圾桶中有可用的，先回收利用 
  return ++x_p;//造新点 
}

建树

线段树基础操作。（需要复习的可以看这里）。

void u_p(int k){//更新节点信息 
  t_r[k].s_m=t_r[t_r[k].l].s_m+t_r[t_r[k].r].s_m;
}
void b_t(int &k,int l=1,int r=n){
  if(!k)k=n_w();//不存在节点，赋予编号 
  if(l==r){
    t_r[k].s_m=a_a[l];//叶节点赋值 
    return;
  }
  int m_i=(l+r)>>1; 
  b_t(t_r[k].l,l,m_i);//左子树 
  b_t(t_r[k].r,m_i+1,r);//右子树 
  u_p(k);//更新节点信息 
}

实现操作一：分裂

分裂的主要思路在于动态开点和值的转移（将原值附在新树上同时清空原点（不是删除））。

注意更新被分裂的线段树节点的值！

void n_t(int &t_1,int &t_2,int x,int y,int l=1,int r=n){//建新树，分裂 
  if(r<x||y<l)return;//不在范围内，返回 
  if(!t_1)return;//树不存在，返回 
  if(x<=l&&r<=y){//在范围内 
    t_2=t_1;//节点赋值 
    t_1=0;//原节点清空 
    return;
  }
  if(!t_2)t_2=n_w();//节点不存在，建新点 
  int m_i=(l+r)>>1;
  n_t(t_r[t_1].l,t_r[t_2].l,x,y,l,m_i);//左子树分裂 
  n_t(t_r[t_1].r,t_r[t_2].r,x,y,m_i+1,r);//右子树分裂 
  u_p(t_1);//更新节点 
  u_p(t_2);//更新节点 
}

实现操作二：合并

合并的思路与分裂的思路很像但区别在于，节点要删除。原因在于题干：（数据保证在此后的操作中不会出现可重集 $t$）。

所以，这些空出来的节点就可以直接回收了。不仅要删叶节点，要删所有的节点。

void b_g(int &t_1,int &t_2,int l=1,int r=n){//线段树合并 
  if(!t_1||!t_2){//有一棵不存在 
    t_1+=t_2;//直接赋值 
    return;
  }
  if(l==r){//是叶节点，合并 
    t_r[t_1].s_m+=t_r[t_2].s_m;
    d_l(t_2);//删掉被合并的节点（叶子结点） 
    return;
  }
  int m_i=(l+r)>>1;
  b_g(t_r[t_1].l,t_r[t_2].l,l,m_i);//左子树合并 
  b_g(t_r[t_1].r,t_r[t_2].r,m_i+1,r);//右子树合并 
  d_l(t_2);//删掉被合并的节点（区间节点） 
  u_p(t_1);//更新节点信息 
}

实现操作三：插入

找到子叶编号为 $q$ 的叶子，将他的权值（或者说个数）加上 $x$ 即可。

void a_d(int n_m,int v,int &k,int l=1,int r=n){
  if(n_m<l||n_m>r)return;//不在范围内返回 
  if(!k)k=n_w();//节点不存在，新建节点 
  if(l==r){//找到叶子结点 
    t_r[k].s_m+=v;//加权（增加数量） 
    return;
  }
  int m_i=(l+r)>>1;
  a_d(n_m,v,t_r[k].l,l,m_i);//左子树维护 
  a_d(n_m,v,t_r[k].r,m_i+1,r);//右子树维护 
  u_p(k);//更新节点信息 
}

实现操作四：查找区间数的个数

线段树区间和操作。

long long s_a(int x,int y,int k,int l=1,int r=n){
  if(y<l||r<x)return 0;//区间外，返回 
  if(!k)return 0;//节点不存在，返回 
  if(x<=l&&r<=y)return t_r[k].s_m;//被范围包含，返回个数 
  int m_i=(l+r)>>1;
  return s_a(x,y,t_r[k].l,l,m_i)+s_a(x,y,t_r[k].r,m_i+1,r);//返回左右子树符合要求的和（此节点的子树总贡献） 
}

实现操作五：根据排名找原数

本操作用到了平衡树的思想，如果左区间的大小比 $k$ 大，那么排名为 $k$ 的值一定在其中，否则减去左子树的大小（左边的数排名一定比它小），跳到右子树继续找。

int f_k(long long p_k,int k,int l=1,int r=n){
  if(p_k<=0)return -1;//未找到，直接返回 
  if(l==r)return l;//找到节点，返回值 
  int m_i=(l+r)>>1;
  if(t_r[t_r[k].l].s_m>=p_k)return f_k(p_k,t_r[k].l,l,m_i);//左子树的数量超过 k 的排名数，一定在左子树 
  return f_k(p_k-t_r[t_r[k].l].s_m,t_r[k].r,m_i+1,r);//减去左子树的数的数量，在右子树继续找 
}

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
}
const int o_o=6e5+10;//数组大小 
int n,m;//序列长度，操作次数 
struct po{
  int l,r;//线段树节点左右边界 
  long long s_m;//区间和 
}t_r[o_o<<2];
int x_p=0;//所有节点个个数（包括垃圾桶中的点） 
int s_m=0;//垃圾桶中可用的点 
int r_s[o_o<<2];//节点垃圾桶 
int r_t[o_o];//记录每个序列的线段树根节点 
int x_t=1;//新可重集序号 
int a_a[o_o];//原序列 
void d_l(int &k){//删除节点 
  t_r[k].l=t_r[k].r=t_r[k].s_m=0;//清空数据 
  r_s[++s_m]=k;//放入垃圾桶 
  k=0;//节点编号清空 
}
int n_w(){//赋新节点编号 
  if(s_m)return r_s[s_m--];//垃圾桶中有可用的，先回收利用 
  return ++x_p;//造新点 
}
void u_p(int k){//更新节点信息 
  t_r[k].s_m=t_r[t_r[k].l].s_m+t_r[t_r[k].r].s_m;
}
void b_t(int &k,int l=1,int r=n){
  if(!k)k=n_w();//不存在节点，赋予编号 
  if(l==r){
    t_r[k].s_m=a_a[l];//叶节点赋值 
    return;
  }
  int m_i=(l+r)>>1; 
  b_t(t_r[k].l,l,m_i);//左子树 
  b_t(t_r[k].r,m_i+1,r);//右子树 
  u_p(k);//更新节点信息 
}
void b_g(int &t_1,int &t_2,int l=1,int r=n){//线段树合并 
  if(!t_1||!t_2){//有一棵不存在 
    t_1+=t_2;//直接赋值 
    return;
  }
  if(l==r){//是叶节点，合并 
    t_r[t_1].s_m+=t_r[t_2].s_m;
    d_l(t_2);//删掉被合并的节点（叶子结点） 
    return;
  }
  int m_i=(l+r)>>1;
  b_g(t_r[t_1].l,t_r[t_2].l,l,m_i);//左子树合并 
  b_g(t_r[t_1].r,t_r[t_2].r,m_i+1,r);//右子树合并 
  d_l(t_2);//删掉被合并的节点（区间节点） 
  u_p(t_1);//更新节点信息 
}
void n_t(int &t_1,int &t_2,int x,int y,int l=1,int r=n){//建新树，分裂 
  if(r<x||y<l)return;//不在范围内，返回 
  if(!t_1)return;//树不存在，返回 
  if(x<=l&&r<=y){//在范围内 
    t_2=t_1;//节点赋值 
    t_1=0;//原节点清空 
    return;
  }
  if(!t_2)t_2=n_w();//节点不存在，建新点 
  int m_i=(l+r)>>1;
  n_t(t_r[t_1].l,t_r[t_2].l,x,y,l,m_i);//左子树分裂 
  n_t(t_r[t_1].r,t_r[t_2].r,x,y,m_i+1,r);//右子树分裂 
  u_p(t_1);//更新节点 
  u_p(t_2);//更新节点 
}
void a_d(int n_m,int v,int &k,int l=1,int r=n){
  if(n_m<l||n_m>r)return;//不在范围内返回 
  if(!k)k=n_w();//节点不存在，新建节点 
  if(l==r){//找到叶子结点 
    t_r[k].s_m+=v;//加权（增加数量） 
    return;
  }
  int m_i=(l+r)>>1;
  a_d(n_m,v,t_r[k].l,l,m_i);//左子树维护 
  a_d(n_m,v,t_r[k].r,m_i+1,r);//右子树维护 
  u_p(k);//更新节点信息 
}
long long s_a(int x,int y,int k,int l=1,int r=n){
  if(y<l||r<x)return 0;//区间外，返回 
  if(!k)return 0;//节点不存在，返回 
  if(x<=l&&r<=y)return t_r[k].s_m;//被范围包含，返回个数 
  int m_i=(l+r)>>1;
  return s_a(x,y,t_r[k].l,l,m_i)+s_a(x,y,t_r[k].r,m_i+1,r);//返回左右子树符合要求的和（此节点的子树总贡献） 
}
int f_k(long long p_k,int k,int l=1,int r=n){
  if(p_k<=0)return -1;//未找到，直接返回 
  if(l==r)return l;//找到节点，返回值 
  int m_i=(l+r)>>1;
  if(t_r[t_r[k].l].s_m>=p_k)return f_k(p_k,t_r[k].l,l,m_i);//左子树的数量超过 k 的排名数，一定在左子树 
  return f_k(p_k-t_r[t_r[k].l].s_m,t_r[k].r,m_i+1,r);//减去左子树的数的数量，在右子树继续找 
}
int main(){
  n=r_r(),m=r_r();
  for(int i=1;i<=n;i++)a_a[i]=r_r();//读入序列 
  b_t(r_t[1]);//以 1 为根节点建树 
  for(int i=1;i<=m;i++){
    int op=r_r();
    if(op==0){
      int p=r_r(),x=r_r(),y=r_r();
      n_t(r_t[p],r_t[++x_t],x,y);//建新树 
    }else if(op==1){
      int p=r_r(),t=r_r();
      b_g(r_t[p],r_t[t]);//合并可重集 
    }else if(op==2){
      int p=r_r(),x=r_r(),q=r_r();
      a_d(q,x,r_t[p]);//加数字 
    }else if(op==3){
      int p=r_r(),x=r_r(),y=r_r();
      printf("%lld\n",s_a(x,y,r_t[p]));//查询范围内数的个数 
    }else {
      int a_s=0;
      int p=r_r(),k=r_r();
      if(s_a(1,n,r_t[p])<k)a_s=-1;//总数不够 k 个，不存在第 k 小 
      else a_s=f_k(k,r_t[p]);//查找第 k 小 
      printf("%d\n",a_s);
    }
  }
  return 0;
}