MnZn求问，为什么是主席树

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
const int N=3e5+10;
int root[N],col[N],tot=0;
struct node{
	int ls,rs,sum;
}a[N<<5];
void update(int &x,int p,int l,int r,int w){
	if(!p) return;
	if(!x) x=++tot;
	a[x].sum+=w;
	if(l==r) return;
	int mid=l+r>>1;
	if(p<=mid) update(a[x].ls,p,l,mid,w);
	else update(a[x].rs,p,mid+1,r,w);
}
int query(int x,int l,int r,int L,int R){
	if(!x) return 0;
	if(L<=l&&r<=R) return a[x].sum;
	int mid=l+r>>1,res=0;
	if(L<=mid) res+=query(a[x].ls,l,mid,L,R);
	if(R>mid) res+=query(a[x].rs,mid+1,r,L,R);
	return res;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1,c;i<=n;i++){
		cin>>c;
		col[i]=c;
		update(root[c],i,1,n,1);
	}
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			int l,r,c;
			cin>>l>>r>>c;
			cout<<query(root[c],1,n,l,r)<<"\n";
		}else{
			int x;
			cin>>x;
			update(root[col[x]],x,1,n,-1);
			update(root[col[x+1]],x+1,1,n,-1);
			update(root[col[x]],x+1,1,n,1);
			update(root[col[x+1]],x,1,n,1);
			swap(col[x],col[x+1]);
		}
	}
	return 0;
}