1 Byte = 8 Bit
1 KB = 1,024 Bytes
1 MB = 1,024 KB = 1,048,576 Bytes
一个int是4字节即4Byte.
求个数和求和类似，不过是在更新的时候把1变成了这个数的值，下面就讲讲求区间不同数字的个数。
首先我们思考对于右端点固定的区间（即R确定的区间），我们如何使用线段树来解决这个问题。
我们可以记录每个数字最后一次出现的位置。比如，5这个数字最后一次出现在位置3上，就把位置3记录的信息++（初始化为0）。比如有一个序列 1 2 2 1 3 那么我们记录信息的数列就是 0 0 1 1 1 （2最后出现的位置是位置3 1最后出现的位置是位置4 3最后出现的位置是位置5）。那么对区间 [1,5] , [2,5] , [3,5] , [4,5] , [5,5]的数字种数，我们都可以用sum[5]-sum[x-1]来求（sum数组记录的是前缀和）（前缀和之差可以用线段树或者树状数组来求）。
那么对着区间右端点会变化的题目，我们应该怎么办呢？先思考一下如果右端点有序的话，我们可以怎么做。对R不同的区间，向线段树或者树状数组中添加元素，知道右端点更新为新的R，在添加的过程中，如果这个元素之前出现过，就把之前记录的位置储存的信息 -1，然后在新的位置储存的信息 +1，这样就可以保证在新的右端点固定的区间里，记录的是数字最后一次出现的位置的信息，这样题目就解决了。
也就是说对于这个题目，我们也可以不用主席树，只要对询问排序，然后利用树状数组或者线段树就可以解决这个问题。（离线解法）
如果不对询问排序的话，我们就必须要用主席树来解决这个问题了，对每个右端点建立一个线段树。不断查询即可。（在线解法）
SPOJ-DQUERY
给你 n 个数，然后有 q 个询问，每个询问会给你[l,r]，输出[l,r]之间有多少种数字。
#include<bits/stdc++.h>//主席树
using namespace std;
#define ll long long
#define fuck(x) cout<<#x<<" "<<x<<endl;
const int maxn=30000+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
int a[maxn],v[maxn],rt[maxn],vis[(int)1e6+10],tot,n;
struct node
{
int ls,rs,sum;
node(int ls=0,int rs=0,int sum=0)
{
this->ls=ls;
this->rs=rs;
this->sum=sum;
}
}tree[maxn*30];
int build1(int l,int r)
{
int t=++tot;
tree[t].sum=0;
if(l!=r)
{
int mid=(l+r)>>1;
tree[t].ls=build1(l,mid);
tree[t].rs=build1(mid+1,r);
}
return t;
}
int build2(int l,int r,int last,int pos,int val)
{
int t=++tot;
tree[t]=tree[last];
tree[t].sum+=val;
if(l!=r)
{
int mid=(l+r)>>1;
if(pos<=mid)
tree[t].ls=build2(l,mid,tree[last].ls,pos,val);
else
tree[t].rs=build2(mid+1,r,tree[last].rs,pos,val);
}
return t;
}
int query(int L,int R,int l,int r,int t)
{
if(l<=L&&r>=R)
return tree[t].sum;
int mid=(L+R)>>1,ans=0;
if(r<=mid)
ans+=query(L,mid,l,r,tree[t].ls);
else
if(l>mid)
ans+=query(mid+1,R,l,r,tree[t].rs);
else
{
ans+=query(L,mid,l,r,tree[t].ls);
ans+=query(mid+1,R,l,r,tree[t].rs);
}
return ans;
}
int main()
{
int n,q;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&(a[i]));
scanf("%d",&q);
rt[0]=build1(1,n);
for(int i=1;i<=n;i++)
{
if(!vis[a[i]])
rt[i]=build2(1,n,rt[i-1],i,1);
else
{
rt[i]=build2(1,n,rt[i-1],vis[a[i]],-1);
rt[i]=build2(1,n,rt[i],i,1);
}
vis[a[i]]=i;
}
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d
",query(1,n,x,y,rt[y]));
}
return 0;
}
给一段n长度的数字序列，以及q次区间询问，问区间不同数字大小之和。
#include<bits/stdc++.h>//主席树
using namespace std;
#define ll long long
#define fuck(x) cout<<#x<<" "<<x<<endl;
const int maxn=30000+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
int a[maxn],rt[maxn],vis[maxn],lsh[maxn],acnt,tot,n;
struct node
{
int ls,rs;
ll sum;
node(int ls=0,int rs=0,ll sum=0)
{
this->ls=ls;
this->rs=rs;
this->sum=sum;
}
}tree[maxn*40];
inline int getid(int x){return lower_bound(lsh+1,lsh+acnt+1,x)-lsh;}
int build1(int l,int r)
{
int t=++tot;
tree[t].sum=0;
if(l!=r)
{
int mid=(l+r)>>1;
tree[t].ls=build1(l,mid);
tree[t].rs=build1(mid+1,r);
}
return t;
}
int build2(int l,int r,int last,int pos,int val)
{
int t=++tot;
tree[t]=tree[last];
tree[t].sum+=1LL*val*a[pos];
if(l!=r)
{
int mid=(l+r)>>1;
if(pos<=mid)
tree[t].ls=build2(l,mid,tree[last].ls,pos,val);
else
tree[t].rs=build2(mid+1,r,tree[last].rs,pos,val);
}
return t;
}
ll query(int L,int R,int l,int r,int t)
{
if(l<=L&&r>=R)
return tree[t].sum;
int mid=(L+R)>>1;
ll ans=0;
if(r<=mid)
ans+=query(L,mid,l,r,tree[t].ls);
else
if(l>mid)
ans+=query(mid+1,R,l,r,tree[t].rs);
else
{
ans+=query(L,mid,l,r,tree[t].ls);
ans+=query(mid+1,R,l,r,tree[t].rs);
}
return ans;
}
int main()
{
int t,n,q;
scanf("%d",&t);
while(t--){
// fuck(1);
acnt=tot=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&(a[i])),lsh[++acnt]=a[i];
sort(lsh+1,lsh+acnt+1);
acnt=unique(lsh+1,lsh+acnt+1)-lsh-1;
for(int i=1;i<=acnt;i++) vis[i]=0;
rt[0]=build1(1,n);
//fuck(2);
for(int i=1;i<=n;i++)
{
int newid=getid(a[i]);
if(!vis[newid])
rt[i]=build2(1,n,rt[i-1],i,1);
else
{
rt[i]=build2(1,n,rt[i-1],vis[newid],-1);
rt[i]=build2(1,n,rt[i],i,1);
}
vis[newid]=i;
}
//fuck(3);
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld
",query(1,n,x,y,rt[y]));
}
//fuck(4);
}
return 0;
}#include<bits/stdc++.h>//线段树
using namespace std;
#define ls rt<<1
#define rs (rt<<1)+1
#define fuck(x) cout<<#x<<" "<<x<<endl;
typedef long long ll;
const int maxn=3e4+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
int x,y,id;
friend bool operator<(const node&aa,const node&bb)
{
return aa.y<bb.y;
}
}qy[(int)1e5+10];
int a[maxn],lsh[maxn],vis[maxn],acnt;
ll sum[maxn<<2],ans[(int)1e5+10];
int getid(int x)
{
return lower_bound(lsh+1,lsh+acnt+1,x)-lsh;
}
void update(int rt,int L,int R,int pos,int val)
{
sum[rt]+=1LL*val*a[pos];
if(L!=R)
{
int mid=(L+R)>>1;
if(pos<=mid)
update(ls,L,mid,pos,val);
else
update(rs,mid+1,R,pos,val);
}
}
ll query(int rt,int L,int R,int l,int r)
{
if(l<=L&&r>=R)
return sum[rt];
int mid=(L+R)>>1;
ll ans=0LL;
if(r<=mid)
ans=query(ls,L,mid,l,r);
else
if(l>mid)
ans=query(rs,mid+1,R,l,r);
else
{
ans=query(ls,L,mid,l,r);
ans+=query(rs,mid+1,R,l,r);
}
return ans;
}
int main()
{
int t,n,q,now;
scanf("%d",&t);
while(t--)
{
now=1;
memset(sum,0,sizeof(sum));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&(a[i])),lsh[i]=a[i];
sort(lsh+1,lsh+n+1);
acnt=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=acnt;i++) vis[i]=0;
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&(qy[i].x),&(qy[i].y));
qy[i].id=i;
}
sort(qy+1,qy+q+1);
for(int i=1;i<=q;i++)
{
while(now<=qy[i].y)
{
int newid=getid(a[now]);
if(!vis[newid])
update(1,1,n,now,1);
else
{
update(1,1,n,vis[newid],-1);
update(1,1,n,now,1);
}
vis[newid]=now++;
}
ans[qy[i].id]=query(1,1,n,qy[i].x,qy[i].y);
}
for(int i=1;i<=q;i++)printf("%lld
",ans[i]);
}
return 0;
}