静态主席树：https://www.cnblogs.com/LonecharmRiver/articles/9087536.html
看看就好
动态主席树：https://blog.csdn.net/WilliamSun0122/article/details/77885781
在里面说一说程序流程
为了完成单点修改的工作，我们需要用另外一堆线段树用树状数组的方式维护
这些线段树的初始形态都是空，即S[0~num]=T[0]
T为维护点权的主席树，S为维护树状数组的主席树
这里离散化建树过程和静态主席树有一点不同，我们必须把所有询问先存起来并且把改变的数也加入到原序列中再离散化建树，会导致空间复杂度和静态有所区别（之前讲静态的时候提过）。所以这里我们离散化后序列为3 2 1 4 6 5分别对应原序列的3 2 1 4 7和改变后的6。
之后同静态一样建空树，按原序列前缀建树。
建好之后，当单点修改的时候，我们按照树状数组的思想，将T[x]的lowbit(x)的修改在这棵树中呈现，比如：
对于C 2 6 这个操作， 我们只需要减去一个2，加上一个5（对应改变后的6）即可。
这个更新我们按树状数组的思想更新，比如这里的减2，我们要从i=2（原序列中第2个数2在离散化后序列中的位置）即S[2]开始更新，并往上lowbit(i)直到大于5，这里我们会更新S[2]和S[4]。
更新操作就告一段落了，然后是查询
对于主席树区间 [l,r] 我们将静态主席树的查询值与以树状数组维护的主席树的值相加即是答案
上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define lowbit(x) x&(-x)
#define MAXN 60050
using namespace std;
int t,n,num,sz[MAXN],b[MAXN],m,T[50060],S[50060],ul[50050],ur[50050];
struct ***_TREE{
int ls[MAXN*32],rs[MAXN*32],sum[MAXN*32],tot;
void init(){
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
memset(sum,0,sizeof(sum));
tot=0;
}
void build(int &rt,int l,int r){
rt=++tot;
if(l==r) return;
int mid=(l+r)>>1;
build(ls[rt],l,mid); build(rs[rt],mid+1,r);
sum[rt]=0;
}
void insert(int &rt,int k,int l,int r,int x,int y){
rt=++tot;
ls[rt]=ls[k]; rs[rt]=rs[k];
sum[rt]=sum[k]+y;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) insert(ls[rt],ls[k],l,mid,x,y);
else insert(rs[rt],rs[k],mid+1,r,x,y);
}
void add(int x,int val){
int res=lower_bound(b+1,b+num+1,sz[x])-b;
while(x<=n){
insert(S[x],S[x],1,num,res,val);
x+=lowbit(x);
}
}
int fsum(int x,bool g){
int res=0;
while(x){
if(g) res+=sum[ls[ur[x]]];
else res+=sum[ls[ul[x]]];
x-=lowbit(x);
}
return res;
}
int query(int s,int e,int x,int y,int l,int r,int k){
if(l==r) return b[l];
int res=fsum(e,1)-fsum(s,0)+sum[ls[y]]-sum[ls[x]],mid=(l+r)>>1;
if(res>=k){
for(int j=s;j;j-=lowbit(j)) ul[j]=ls[ul[j]];
for(int j=e;j;j-=lowbit(j)) ur[j]=ls[ur[j]];
return query(s,e,ls[x],ls[y],l,mid,k);
}
else{
for(int j=s;j;j-=lowbit(j)) ul[j]=rs[ul[j]];
for(int j=e;j;j-=lowbit(j)) ur[j]=rs[ur[j]];
return query(s,e,rs[x],rs[y],mid+1,r,k-res);
}
}
}Q;
struct zlk{
int l,r,k;
bool flag;
}wyx[10050];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
Q.init(); num=0;
rep(i,1,n){
scanf("%d",&sz[i]); b[++num]=sz[i];
}
rep(i,1,m){
char ch=getchar();
while(ch!='Q' && ch!='C') ch=getchar();
if(ch=='Q'){
scanf("%d%d%d",&wyx[i].l,&wyx[i].r,&wyx[i].k);
wyx[i].flag=1;
}
else{
scanf("%d%d",&wyx[i].l,&wyx[i].r);
wyx[i].flag=0;
b[++num]=wyx[i].r;
}
}
sort(b+1,b+num+1);
int tmp=unique(b+1,b+num+1)-(b+1);
num=tmp;
Q.build(T[0],1,num);
rep(i,1,n) S[i]=T[0],Q.insert(T[i],T[i-1],1,num,lower_bound(b+1,b+num+1,sz[i])-b,1);
rep(i,1,m){
if(wyx[i].flag){
for(int j=wyx[i].l-1;j;j-=lowbit(j)) ul[j]=S[j];
for(int j=wyx[i].r;j;j-=lowbit(j)) ur[j]=S[j];
printf("%d\n",Q.query(wyx[i].l-1,wyx[i].r,T[wyx[i].l-1],T[wyx[i].r],1,num,wyx[i].k));
}
else{
Q.add(wyx[i].l,-1);
sz[wyx[i].l]=wyx[i].r;
Q.add(wyx[i].l,1);
}
}
}
return 0;
}
一道例题：HH的项链
题目背景
无
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入样例#1：
6 1 2 3 4 3 5 3 1 2 3 5 2 6输出样例#1：
2 2 4
说明
数据范围：
对于100%的数据，N <= 500000，M <= 500000。
我们统计出来每种颜色的贝壳下一次出现的位置，若之后没有了则为n+1，记为nxt[i]，然后查询区间[l,r]，就相当于查询在区间[l,r]之间，有多少个数的nxt值大于等于r+1，这个问题非常容易解决，然后就好了。？
算过数据范围的，你会发现，nlogn就将近1亿了，但是主席树呢需要2*nlogn，所以你需要卡常
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define mid ((l+r)>>1)
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define MAXN 500001
#define MAXM 9970005
#define MAXL 1000001
using namespace std;
int ls[MAXM],rs[MAXM],sum[MAXM];
int tot;
inline int read(){
register int x(0);
char ch(getchar());
while('0'>ch || ch>'9')ch=getchar();
while('0'<=ch && ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
return x;
}
struct ***_TREE{
inline void insert(register int &k,register int kk,register int l,register int r,register int x,register int val){
k=++tot;
sum[k]=sum[kk]+val;
if(l==r) return;
ls[k]=ls[kk],rs[k]=rs[kk];
if(x<=mid) insert(ls[k],ls[kk],l,mid,x,val);
else insert(rs[k],rs[kk],mid+1,r,x,val);
}
inline int asks(register int k,register int kk,register int l,register int r,register int t){
if(l==r) return sum[k]-sum[kk];
if(t<=mid) return asks(ls[k],ls[kk],l,mid,t)+sum[rs[k]]-sum[rs[kk]];
else return asks(rs[k],rs[kk],mid+1,r,t);
}
}Q;
inline void print(register int x){
register int t(10);
while(x>=t) t*=10;t/=10;
while(t){
putchar(48+int(x/t));
x%=t;
t/=10;
}
putchar('\n');
}
int fir[MAXL],T[MAXN],m,nxt[MAXN],n,a[MAXN];
int main(){
n=read();
rep(i,1,n){
a[i]=read();
if(fir[a[i]]) nxt[fir[a[i]]]=i;
fir[a[i]]=i;
}
rep(i,1,n) if(!nxt[i]) nxt[i]=n+1;
rep(i,1,n) Q.insert(T[i],T[i-1],1,n+1,nxt[i],1);
m=read();
rep(i,1,m){
register int l(read()),r(read());
print(Q.asks(T[r],T[l-1],1,n+1,r+1));
}
return 0;
}
标签：rt,专题,int,rep,wyx,num,树小,include,主席 From： https://www.cnblogs.com/handsome-zlk/p/10436634.html