线段树与可持久化

单点更新

成都地区优秀IDC服务器托管提供商(成都创新互联).为客户提供专业的四川雅安服务器托管,四川各地服务器托管,四川雅安服务器托管、多线服务器托管.托管咨询专线：18982081108

/*
* @Author: qin_peng
* @Date:   2018-08-20 23:22:08
* @Last Modified by:   qin_peng
* @Last Modified time: 2018-08-29 23:22:34
*/
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=55555;
int sum[maxn<<2]={0};
void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void build(int l,int r,int rt)
{
    if(l==r){scanf("%d",&sum[rt]);return ;}
    int m=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
void update(int pos,int val,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=val;return ;
    }
    int m=(l+r)>>1;
    if(pos<=m)update(pos,val,lson);
    else update(pos,val,rson);pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l and r<=R)return sum[rt]; 
    int m=(l+r)>>1;
    int res=0;
    if(L<=m)res+=query(L,R,lson); 
    if(R>m)res+=query(L,R,rson);
    return res;
}

区间更新

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=200005;
ll sum[maxn<<2|1]={0};
ll add[maxn<<2|1]={0};
void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
void pushdown(int rt,int m)
{
    if(add[rt])
    {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=add[rt]*(m-(m>>1));
        sum[rt<<1|1]+=add[rt]*(m>>1);
        add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    if(l==r){scanf("%lld",&sum[rt]);return;}
    int m=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
    if(l>=L and r<=R)
    {
        add[rt]+=val;
        sum[rt]+=(ll)val*(r-l+1);return ;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m)update(L,R,val,lson);
    if(m=r)return sum[rt];
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    ll res=0;
    if(m>=L)res+=query(L,R,lson);
    if(m
区间合并
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=5e4+10;
int lsum[N<<2],rsum[N<<2],head[N],n,q;
void push_up(int rt,int m)
{
    lsum[rt]=lsum[rt<<1];
    rsum[rt]=rsum[rt<<1|1];
    if(lsum[rt<<1]==m-(m>>1))lsum[rt]+=lsum[rt<<1|1];
    if(rsum[rt<<1|1]==m>>1)rsum[rt]+=rsum[rt<<1];
}
void build(int l,int r,int rt)
{
    lsum[rt]=rsum[rt]=r-l+1;
    if(l==r)return ;
    int m=l+r>>1;
    build(lson),build(rson);
}
void update(int p,int val,int l,int r,int rt)
{
    if(l==r){lsum[rt]=rsum[rt]=val;return;}
    int m=l+r>>1;
    if(p<=m)update(p,val,lson);
    else update(p,val,rson);
    push_up(rt,r-l+1);
}
int query(int p,int l,int r,int rt)
{
    if(l==r)return 0;
    int m=l+r >>1;
    if(p>=m-rsum[rt<<1]+1&&p<=m+lsum[rt<<1|1])
    return rsum[rt<<1]+lsum[rt<<1|1];
    if(p<=m) return query(p,lson);
    else return query(p,rson);
}
经典染色
#include  
#include  
#include  
#include  
#include  
#define MAXN 40010  
#define inf 0x3f3f3f3f  
using namespace std;  
int li[MAXN];
int ri[MAXN];
int lisan[MAXN<<2];
int tree[MAXN<<2]; 
int vis[MAXN<<2];
int ans;
void pushdown(int p)
{
    tree[p<<1]=tree[(p<<1)|1]=tree[p];
    tree[p]=-1;
}
void update(int p,int l,int r,int x,int y,int a)
{
    if(x<=l&&y>=r)
    {
        tree[p]=a;
        return ;
    }
    if(tree[p]!=-1)
    pushdown(p);
    int mid=(l+r)>>1;   if(y<=mid)
    update(p<<1,l,mid,x,y,a);
    else if(x>mid)
    update((p<<1)|1,mid+1,r,x,y,a);
    else
    {
        update(p<<1,l,mid,x,mid,a);
        update((p<<1)|1,mid+1,r,mid+1,y,a);
    }
}
void query(int p,int l,int r)
{
    if(l==r)
    {
        if(!vis[tree[p]]&&tree[p]!=-1)
        {
           ans++;
           vis[tree[p]]=1;
        }
        return ;
    }
    if(tree[p]!=-1)
    pushdown(p);
    int mid=(l+r)>>1;
    query(p<<1,l,mid);
    query((p<<1)|1,mid+1,r);
}
int main()  
{  
    int t;
    scanf("%d",&t);
    int n;
    while(t--)
    {
        scanf("%d",&n);
        memset(tree,-1,sizeof(tree));
        memset(vis,0,sizeof(vis));
        int tot=0;
        for(int i=0;i1)
            {
                lisan[m++]=lisan[i-1]+1;
            }
        }
        sort(lisan,lisan+m);
        for(int i=0;i
主席树
#include
#include
#include
#define mid (l+r)/2
using namespace std;
const int N = 100010;
int n, q, m, cnt = 0;
int a[N], b[N], T[N];
int sum[N<<5], L[N<<5], R[N<<5];
int getid(int x){return lower_bound(b+1,b+1+m,x)-b;}
inline int build(int l, int r)
{
    int rt = ++ cnt;
    sum[rt] = 0;
    if (l < r){
        L[rt] = build(l, mid);
        R[rt] = build(mid+1, r);
    }
    return rt;
}
inline int update(int pre, int l, int r, int x)
{
    int rt = ++ cnt;
    L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre]+1;
    if (l < r){
        if (x <= mid) L[rt] = update(L[pre], l, mid, x);
        else R[rt] = update(R[pre], mid+1, r, x);
    }
    return rt;
}
inline int query(int u, int v, int l, int r, int k)
{
    if (l >= r) return l;
    int x = sum[L[v]] - sum[L[u]];
    if (x >= k) return query(L[u], L[v], l, mid, k);
    else return query(R[u], R[v], mid+1, r, k-x);
}
int main()
{
 int t;scanf("%d",&t);
 while(t--){
  cnt=0;
     scanf("%d%d", &n, &q);
     for (int i = 1; i <= n; i ++){
         scanf("%d", &a[i]);
         b[i] = a[i];
     }
     sort(b+1, b+1+n);
     m = unique(b+1, b+1+n)-b-1;
     T[0] = build(1, m);
     for (int i = 1; i <= n; i ++){
         T[i] = update(T[i-1], 1, m, getid(a[i]));
     }
     while (q --){
         int x, y, z;
         scanf("%d%d%d", &x, &y, &z);
         printf("%d\n", b[query(T[x-1], T[y], 1, m, z)]);
     }
 }
}
动态可持久化线段树
#include
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
#define lson l,mid
#define rson mid+1,r
using namespace std;
const int o_o=6e4+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
int n,m,sz;
int Hash[o_o],a[o_o],cnt=0;
int root[o_o<<5],T[o_o],S[o_o];
int L[o_o<<5],R[o_o<<5],UR[o_o],UL[o_o];
struct node{
 int flag;
 int id,val;
 int l,r,k;
}Q[10005];
int getid(int x){return lower_bound(Hash+1,Hash+1+sz,x)-Hash;}
int build(int l,int r){
 int rt=++cnt;
 root[rt]=0;
 int mid=l+r>>1;
 if(l>1;
 if(l>=r)return rt;
 if(l>1;
 if(l>=r)return l;
 if(k<=num){
  for(int i=ed;i;i&=i-1)UR[i]=L[UR[i]];
  for(int i=st;i;i&=i-1)UL[i]=L[UL[i]];
  return query(st,ed,L[u],L[v],lson,k);
 }else{
  for(int i=ed;i;i&=i-1)UR[i]=R[UR[i]];
  for(int i=st;i;i&=i-1)UL[i]=R[UL[i]];
  return query(st,ed,R[u],R[v],rson,k-num);
 }
}
int main(){
 int t;cin>>t;
 while(t--){
  cnt=0;
  scanf("%d%d",&n,&m);sz=n;
  for(int i=1;i<=n;i++)scnaf("%d",a+i),Hash[i]=a[i];
  for(int i=1;i<=m;i++){
   char str[2];
   scnaf("%s",str);
   if(str[0]=='Q'){
    Q[i].flag=true;
    scnaf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
   }else{
    int pos,val;
    scnaf("%d%d",&pos,&val);
    Q[i].flag=false;
    Q[i].id=pos,Q[i].val=val;
    Hash[++sz]=val;
   }
  }
  sort(Hash+1,Hash+1+sz);
  sz=unique(Hash+1,Hash+1+sz)-Hash-1;
  T[0]=build(1,sz);
  for(int i=1;i<=n;i++)T[i]=insert(T[i-1],1,sz,getid(a[i]),1);
  for(int i=0;i<=n;i++)S[i]=T[0];
  for(int i=1;i<=m;i++){
   if(Q[i].flag){
    for(int j=Q[i].r;j;j&=j-1)UR[j]=S[j];
    for(int j=Q[i].l-1;j;j&=j-1)UL[j]=S[j];
    printf("%d\n",Hash[query(Q[i].l-1,Q[i].r,T[Q[i].l-1],T[Q[i].r],1,sz,Q[i].k)]);
   }else{
    add(Q[i].id,-1);
    a[Q[i].id]=Q[i].val;
    add(Q[i].id,1);
   }
  }
 }
}
            
            
                        

            文章题目：线段树与可持久化            

            本文链接：http://cqcxhl.cn/article/jhdjsp.html