一道树状数组的离线询问题
下面简单介绍一下树状数组
如果已经知道树状数组是什么的可以直接跳到分割线后面

树状数组他其实利用的是类似于二进制的东西，所以英文名也叫做BIT(Binary Index Tree)每一次通过lowbit函数求出来当前这个数的所管范围，假设现在的数是x,他的区间就是[x-lowbit(x)+1,x]，那么我们为什么要用这个树状数组呢？或者说它有什么好处吗？
其实树状数组它能解决的问题十分有限，相比较线段树这个数据结构，树状数组只能够处理求区间和的问题，但是不能求解区间的最大值，最小值，异或值等等。那么树状数组和普通的数组查询和修改又有什么不一样的？
很简单，树状数组由于使用的是二进制的原理，那么他每一次的修改操作，查询操作就一定是妥妥的O(nlogn).肯定好于一般的操作了。
下面放一个从百度上面找到的很经典的树状数组的图方便大家理解：

其实树状数组的题目难就难在你要发现它可以使用树状数组来做，其实代码并不难，相比线段树还是要好写一些的。言归正传，这个题要怎么做呢？
我们可以构建一个结构体存储每一次的查询的范围len，查询的编号id，查询的数值x,以及要设置一个flag来代表是左端点还是右端点。因为你如果是左端点的话，你就要减去1，这一点相信大家都知道，因为是前缀和的原理了，就是你要求l到r的和你只需要做sum(r)-sum(l-1)这样就行了。所以如果在设置左端点的时候一定要范围-1。
很关键的一步是要按照每一个结构体的排个序，这样可以保证从前往后扫一遍，不重不漏
，并且使线性的复杂度，整个程序的时间复杂度大概是O((n+m)logn)
之后再从前往后每一次去加入a[i]；进行add(a[i],1)这个操作，每一次求出来这个点之前的所有满足大于x的sum值，就可以了。
详情见代码~

code

#include<bits/stdc++.h>
using namespace std;
int a[100010],n,m;
int l[100010],r[100010],tr[100010];
struct node{
    int len,id,val,flag;
}p[200010];//这里要特别注意要开两倍，不然会数组越界
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(int i=x;i<=100000;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)
{
    if(x==0) return 0;
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int now=1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        p[now++]={x-1,i,z,0};//构建左边的查询点
        p[now++]={y,i,z,1};//构造右边的查询点
}
    sort(p+1,p+1+2*m,[](node a,node b){return a.len<b.len;});//排序比较
    now=1;
    for(int i=0;i<=n;i++)
    {
     if(a[i]!=0)
        add(a[i],1);
        while(p[now].len==i&&now<=2*m){//当这个查询区间的长度为当前的i时候，可以计算得出结果

            if(p[now].flag==1)r[p[now].id]=sum(p[now].val);
                else l[p[now].id]=sum(p[now].val);
            ++now;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<r[i]-l[i]<<endl;//对于每一个区间输出结果
}
    return 0;
}