可修改主席树

普通主席树

---

普通主席树比较简单 就是很多个权值线段树 每一次加进去log个节点（每层一个），剩下的节点用原来的线段树中的节点直接连到新节点上就好了

线段树

image

插入节点

image

主席树

image

主席树拆开之后

image

POJ2104 主席树模板题 代码：

#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;

ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int maxn=100100,maxm=5050;
int n,m,cnt,nums;
int a[maxn],b[maxn],num[maxn],root[maxn];
vector<int> vec;
struct Node{
    int l,r,val;
} tr[maxn*40];

int getid(int x){return int(lower_bound(vec.begin(),vec.end(),x)-vec.begin())+1;}

void update(int l,int r,int &x,int y,int val){
    nums++;tr[nums]=tr[y];tr[nums].val++;x=nums;
    if(l==r) return;
    int md=(l+r)>>1;
    if(val<=md) update(l,md,tr[x].l,tr[y].l,val);
    else update(md+1,r,tr[x].r,tr[y].r,val);
}
int ask(int l,int r,int x,int y,int val){
    if(l==r) return l;
    int md=(l+r)>>1;
    int nw=tr[tr[y].l].val-tr[tr[x].l].val;
    if(val<=nw) return ask(l,md,tr[x].l,tr[y].l,val);
    else return ask(md+1,r,tr[x].r,tr[y].r,val-nw);
}

int main(){
    #ifdef LZT
    //freopen("in","r",stdin);
    #endif
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),vec.push_back(a[i]);
    sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++)
        a[i]=getid(a[i]),update(1,n,root[i],root[i-1],a[i]);
    for(int i=1;i<=m;i++){
        int l=read(),r=read(),k=read();
        printf("%d\n",vec[ask(1,n,root[l-1],root[r],k)-1]);
    }
    return 0;
}j

/*
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
*/

---

可修改主席树

---

其实就是树状数组套主席树

为什么不能直接修改呢？

因为主席树的第i棵树是被第i+1到n棵树包含的

那么每次修改就得把后面的所有的树全部修改一遍

如果运气不好 复杂度可能达到$O(mn \log n)

那么我们需要一个每个点可以通过log的时间算出来并且修改也只需log的时间的东西----->树状数组

ZOJ2112 Dynamic Rankings

这是一道可修改主席树的模板题

目前并没有看出来这个数据结构有什么应用 但是感觉很有用的样子

好像也可以cdq分治+整体二分做

这题比较卡内存 所以初值单独记录在一个线段树中 修改记录在树状数组中 查询的时候综合一下

时间复杂度: O(M×logn×logn+nlogn)

代码:

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<stdio.h>
#include<math.h>
#include <string>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include<utility>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define ll long long int
#define mod 1000000007
#define maxn 60005
#define maxm 2500005
int m,n,nn,tot;
int a[maxn],f[maxn],T[maxn],S[maxn];
int sum[maxm],l[maxm],r[maxm];
int use[maxn];
int h(int x){//该值在离散化后线段树的位置
    return lower_bound(f+1,f+1+nn,x)-f;
}
void update(int pr,int lx,int rx,int v,int k){//插入，即新建第i个线段树
    l[++tot]=l[pr];r[tot]=r[pr];sum[tot]=sum[pr]+k;
    if(lx==rx) return;
    int mid=(lx+rx)>>1;
    if(v<=mid) {
            l[tot]=tot+1;
            update(l[pr],lx,mid,v,k);
    }
    else {
            r[tot]=tot+1;
            update(r[pr],mid+1,rx,v,k);
    }
}
void build(int rt,int lx,int rx){//初始化空树
    sum[rt]=0;
    if(lx==rx) return;
    l[rt]=++tot;
    int mid=(lx+rx)>>1;
    build(tot,lx,mid);
    r[rt]=++tot;
    build(tot,mid+1,rx);
}
int lowbit(int x){return x&(-x);}
int Sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=sum[l[use[i]]];
    return res;
}
void add(int x,int v,int k)
 {
     int tt;
    for(int i=x;i<=n;i+=lowbit(i)){
        tt=S[i];
        S[i]=tot+1;
        update(tt,1,nn,v,k);
    }
 }

int query(int L,int R,int k){
    for(int i=L-1;i;i-=lowbit(i)) use[i]=S[i];//use记录要操作的线段树下标
    for(int i=R;i;i-=lowbit(i)) use[i]=S[i];
    int lx=1,rx=nn;
    int lt=T[L-1],rt=T[R];
    while(lx<rx){
        int mid=(lx+rx)>>1;
        int tmp=Sum(R)-Sum(L-1)+sum[l[rt]]-sum[l[lt]];
        if(k<=tmp){
            rx=mid;
            for(int i=L-1;i;i-=lowbit(i)) use[i]=l[use[i]];
            for(int i=R;i;i-=lowbit(i)) use[i]=l[use[i]];
            lt=l[lt];rt=l[rt];
        }
        else{
            lx=mid+1;k-=tmp;
            for(int i=L-1;i;i-=lowbit(i)) use[i]=r[use[i]];
            for(int i=R;i;i-=lowbit(i)) use[i]=r[use[i]];
            lt=r[lt];rt=r[rt];
        }
    }
    return f[lx];
}
char op[5];
int q[10005][4],t;
int main()
{
    rd(t);
    while(t--){
          rd2(n,m);
          for(int i=1;i<=n;i++) {
                  rd(a[i]);f[i]=a[i];
          }
          nn=n;
          for(int i=1;i<=m;i++){
              scanf("%s",op);
              if(op[0]=='Q') {
                  scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
                  q[i][0]=1;
              }
              else{
                  scanf("%d%d",&q[i][1],&q[i][2]);
                  q[i][0]=0;
                  f[++nn]=q[i][2];
              }
          }
          sort(f+1,f+1+nn);
          nn=unique(f+1,f+1+nn)-f-1;//离散化线段树，并去重
          tot=0;
          T[0]=0;
          build(0,1,nn);
          for(int i=1;i<=n;i++){
              T[i]=tot+1;          //T[i]记录第i个线段树的根
              update(T[i-1],1,nn,h(a[i]),1);
          }
          for(int i=1;i<=n;i++) S[i]=T[0];
         // int L,R,k,x;
          for(int i=1;i<=m;i++){
              if(q[i][0]){
                  printf("%d\n",query(q[i][1],q[i][2],q[i][3]));
              }
              else{
                  add(q[i][1],h(a[q[i][1]]),-1);
                  add(q[i][1],h(q[i][2]),1);
                  a[q[i][1]]=q[i][2];
              }
          }
    }
    return 0;
}