树状数组（离线求区间不同数字个数）

数据结构

树状数组基础知识

树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值。

///(树状数组模板不需要理解记住)
const int maxn = 1e5 + 5;
int lowbit(int x)
{
    return x&(-x);
}
void Add(int pos,int val)///单点修改
{
    for(int i=pos;i<maxn;i+=lowbit(i))
        c[i]+=val;
}
int Sum(int pos)///从0位置到pos位置的区间和
{
    int ret=0;
    for(int i=pos;i>0;i-=lowbit(i))
        ret+=c[i];
    return ret;
}
//sum函数用于求和。给出的数列中前i项的和。若需求某i，j段的和,则用sum[j]-sum[i-1];

power oj-2459：Submissions of online judge

• 样例

输入
2 //t两组测试数据
3 //序列长度为3
1 1 4 //序列
2 //有2次询问
1 2 //区间1-2有几个数字
2 3 //区间2-3有几个数字
5
1 1 2 1 3
3
1 5
2 4
3 5
输出
1
2
3
2
3

解题思路

树状数组离线求区间不同数字个数
用vector来存查询区间以及查询顺序v[r].push_back(make_pair(l,i))，开一个map（lastpose）来存pose点上一次出现的位置（从查询的右区间开始往左走）将往左走第一次出现的数的值修改为1，再往前走重复出现的修改为0，所以在用树状数组求区间和的时候区间和即为区间不同数的个数。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int t,n,q,l,r;
int a[maxn],c[maxn];///a[]原数组,c[]树状数组
int ans[maxn];///询问的结果
vector<pair<int,int> >v[maxn];
///树状数组(区间求和)
int lowbit(int x)
{
    return x&(-x);
}
void Add(int pos,int val)///单点修改
{
    for(int i=pos;i<=n;i+=lowbit(i))
        c[i]+=val;
}
int Sum(int pos)///从0位置到pos位置的区间和
{
    int ret=0;
    for(int i=pos;i>0;i-=lowbit(i))
        ret+=c[i];
    return ret;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            v[i].clear();
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&l,&r);
            v[r].push_back(make_pair(l,i));
        }
        unordered_map<int,int>lastpose;///pose上一次出现的位置
        ///也可以用map,不过unordered_map更快，用数组的话数据太多装不下
        for(int i=1;i<=n;i++)
        {
            if(lastpose[a[i]])///a[i]的上一位存在-1使树状数组中的值为0
                Add(lastpose[a[i]],-1);
            Add(i,1);///最近的这个数在树状数组里修改为1
            lastpose[a[i]]=i;
            for(int j=0;j<v[i].size();j++)
            {
                int L=v[i][j].first;///左区间L
                int R=i;
                int id=v[i][j].second;///第id次询问
                int sum=Sum(R)-Sum(L-1);
                ans[id]=sum;
            }
        }
        for(int i=1;i<=q;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}