本文共 6027 字，大约阅读时间需要 20 分钟。
梦寐中的主席树！啊！原来好简单！（带修其实好难理解
大致知识
普通主席树
- 权值线段树
- 离散化
- 每加一个点新建一条根到叶的路实现用NlogN空间存N个权值线段树
- 查询[x,y]，用第y棵树与第 x − 1 x-1 x−1棵树做差
带修主席树
- 用普通主席树维护原序列
- 用树状数组套主席树保存修改，即树状数组第i点是区间 [ i − l o w b i t ( i ) + 1 , i ] [i-lowbit(i)+1,i] [i−lowbit(i)+1,i]的权值线段树
- 修改就是树状数组上权值线段树的修改。时间复杂度就是 ( log n ) 2 (\log n)^2 (logn)2(树状数组修改*权值线段树修改)
- 查询 [ x , y ] [x,y] [x,y]，原主席树用第y棵树与第 x − 1 x-1 x−1棵树做差，树状数组则用y前缀和减去x-1的前缀和，再综合起来在权值线段树查询 (具体看分析&代码
完事~
Problem List
分析 & 代码
求区间第k小值。
//Luo P3834#include using namespace std;const int maxn=2e5+5;struct ooo{ int l,r,sum;}e[maxn*50];int a[maxn],root[maxn],cnt=0;vector v;int getId(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}void update(int l,int r,int &x,int y,const int &pos){ x=++cnt; e[x]=e[y]; e[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)update(l,mid,e[x].l,e[y].l,pos); else update(mid+1,r,e[x].r,e[y].r,pos);}int query(int l,int r,int x,int y,int k){ if(l==r)return l; int mid=(l+r)>>1; int s=e[e[y].l].sum-e[e[x].l].sum; if(k<=s)return query(l,mid,e[x].l,e[y].l,k); else return query(mid+1,r,e[x].r,e[y].r,k-s);}int main(){ int n,m; scanf("%d%d",&n,&m); v.resize(n); for(int i=0;i
求区间内≤k的数的个数
//HDU 4417#include using namespace std;const int maxn=1e5+5;inline void read(int &x){ x=0; char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9') { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); }}struct ooo{ int l,r,sum;}tree[maxn*50];int cnt=0,root[maxn];vector a,v;int getId(const int &x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }void update(int l,int r,int &x,int y,const int &pos){ x=++cnt; tree[x]=tree[y]; tree[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)update(l,mid,tree[x].l,tree[y].l,pos); else update(mid+1,r,tree[x].r,tree[y].r,pos);}int query(int l,int r,int x,int y,int k)//查询区间内位置比k小的数量 { if(r =k)return 0; int mid=(l+r)>>1; if(k<=mid)return query(l,mid,tree[x].l,tree[y].l,k); else return tree[tree[y].l].sum-tree[tree[x].l].sum+query(mid+1,r,tree[x].r,tree[y].r,k); }int main(){ int n,m,T; read(T); for(int casei=1;casei<=T;casei++) { printf("Case %d:\n",casei); read(n),read(m); v.resize(n); for(int i=0;i
求树上两点之间的边权≤k的边数。树上建主席树+LCA。所谓主席树即可持续化线段树，给序列建主席树->每增加一个数在上一个数的版本上更新版本，而给树建主席树->每个节点在其父节点的版本上更新版本。
//2019ICPC南昌邀请赛网络赛J题 Distance on the tree#include using namespace std;const int maxn=1e5+5;struct Node{ int l,r,sum;}tree[maxn*50];struct Edge{ int to,value;};int dep[maxn],fa[maxn][21],root[maxn],n;vector G[maxn];vector v;int getId(const int &x){ return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}void update(int l,int r,int &x,int y,int pos){ static int cnt=0; x=++cnt; tree[x]=tree[y]; tree[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)update(l,mid,tree[x].l,tree[y].l,pos); else update(mid+1,r,tree[x].r,tree[y].r,pos);}int query(int l,int r,int x,int y,int pos)//查询(x,y]中比pos小的个数 { if(pos>r)return tree[y].sum-tree[x].sum; if(pos<=l)return 0; int mid=(l+r)>>1; if(pos<=mid)return query(l,mid,tree[x].l,tree[y].l,pos); int s=tree[tree[y].l].sum-tree[tree[x].l].sum; return s+query(mid+1,r,tree[x].r,tree[y].r,pos);}void dfs(int u){ for(int i=1;(1< <=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=0;i dep[y])swap(x,y); int f=dep[y]-dep[x]; for(int i=0;(1< <=f;i++) if((1< =0;i--) if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } return fa[x][0];}int main(){ int m,x,y,k; scanf("%d%d",&n,&m); //v.resize(n); for(int i=0;i
带修主席树，个人理解主要是用到了主席树和树状数组的特点巧妙使复杂度变成 O ( n ( log n ) 2 ) O(n(\log n)^2) O(n(logn)2)
//带修主席树 Dynamic Rankings#include #define read(xxx) scanf("%d",&xxx)#define lowbit(xx) (xx&(-xx))#define write(xxx) printf("%d\n",xxx)using namespace std;const int maxn=5e4+5,maxm=1e4+5;struct node{ int l,r,k,op;}q[maxm];//保存查询或修改struct ooo{ int l,r,sum;}tree[(maxn+maxm)*32];int n,m,sz,root[maxn],b[maxn+maxm],a[maxn],s[maxn+maxm],rl[200],rr[200];//a为此时的序列，b为离散化后，s存树状数组,即s[i]为[i-lowbit(i)+1,i]的修改情况//root为原序列主席树根，rl，rr临时存放修改节点的主席树根节点int getId(int x){ return lower_bound(b,b+sz,x)-b+1; }int cnt=0,cntl,cntr;struct Tree{ void update(int l,int r,int &x,int y,int pos)//普通主席树更新 { x=++cnt; tree[x]=tree[y]; tree[x].sum++; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)update(l,mid,tree[x].l,tree[y].l,pos); else update(mid+1,r,tree[x].r,tree[y].r,pos); } void add_update(int l,int r,int &x,int pos,int val)//修改 { if(x==0) { x=++cnt; tree[x].sum=tree[x].l=tree[x].r=0; } tree[x].sum+=val; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid)add_update(l,mid,tree[x].l,pos,val); else add_update(mid+1,r,tree[x].r,pos,val); } void add(int idx,int val) { int x=getId(a[idx]),y=getId(val); a[idx]=val; while(idx<=n) { add_update(1,sz,s[idx],x,-1); add_update(1,sz,s[idx],y,1); idx+=lowbit(idx); } } int query(int l,int r,int x,int y,int k) { if(l==r)return l; int sum=tree[tree[y].l].sum-tree[tree[x].l].sum; for(int i=1;i<=cntl;++i) sum-=tree[tree[rl[i]].l].sum; for(int i=1;i<=cntr;++i) sum+=tree[tree[rr[i]].l].sum; int mid=(l+r)>>1; if(sum>=k) { for(int i=1;i<=cntl;++i) rl[i]=tree[rl[i]].l; for(int i=1;i<=cntr;++i) rr[i]=tree[rr[i]].l; return query(l,mid,tree[x].l,tree[y].l,k); } else { for(int i=1;i<=cntl;++i) rl[i]=tree[rl[i]].r; for(int i=1;i<=cntr;++i) rr[i]=tree[rr[i]].r; return query(mid+1,r,tree[x].r,tree[y].r,k-sum); } } int kth(int l,int r,int k) { cntl=cntr=0; for(int i=l-1;i;i-=lowbit(i)) rl[++cntl]=s[i]; //l-1的前缀和所包含的节点 for(int i=r;i;i-=lowbit(i)) rr[++cntr]=s[i]; //r的前缀和所包含的节点 int ans=query(1,sz,root[l-1],root[r],k); return b[ans-1]; } }tr;void init(){ memset(s,0,sizeof(s)); cnt=0; sz=0;}int main(){ int T; read(T); while(T--){ init(); read(n),read(m); for(int i=1;i<=n;i++) read(a[i]),b[sz++]=a[i]; char tmp; for(int i=0;i
转载地址：http://owuzi.baihongyu.com/