度娘真是个好东西

struct node{    int len;    int tree[1000100];    int lowbit(int x)    {        return x&(-x);    }    void updata(int x,int value)    {        while(x<=len)        {            tree[x]+=value;            x+=lowbit(x);        }    }    int sum(int x)    {        int ans=0;        while(x>0)        {            ans+=tree[x];            x-=lowbit(x);        }        return ans;    }    int check(int x,int y)    {        return sum(y)-sum(x-1);    } };

树状数组可以快速的查询区间和插叙两次

所以我们就可以将被求和换成其他意义的数组，完成不同的任务

比如说区间修改和单点查询（注意这两个是同时存在的），还比如求逆序对

上题

对于逆序对这道题，在桶拍上用树状数组，还需要进行离散化。如果数据范围是int以外，那直接开桶是要炸的 树状数组就是个辣鸡 。

#include
    
     #include
     
      using namespace std;struct haha{    int val;    int hao;};bool compare(haha a,haha b){    return a.val>b.val;}haha in[41000];struct node{    int tree[41000];    int num;    int lowbit(int x)    {        return x&(-x);    }    void updata(int i,int value)    {        while(i<=num)        {            tree[i]+=value;            i+=lowbit(i);        }        return ;    }    int sum(int x)    {        int ans=0;        if(x)            while(x>0)            {                ans+=tree[x];                x-=lowbit(x);            }        return ans;    }    int check(int x,int y)     {        return sum(y)-sum(x-1);    }};node bit;int cym[41000],da=0,h=0;int main(){    cin.sync_with_stdio(false);//没错，我就是懒    /*freopen("testdata.in","r",stdin);    freopen("testdata.out","w",stdout);*/    int n;    cin>>n;    bit.num=n;    int ans=0;    for(int i=1;i<=n;i++)    {        cin>>in[i].val;        in[i].hao=i;    }     sort(in+1,in+n+1,compare);    for(int i=1;i<=n;i++)    {        if(h!=in[i].val)        {            da++;//第几大            h=in[i].val;//如果有重复的就是一样大        }        cym[in[i].hao]=da;    }    for(int i=1;i<=n;i++)//顺序插入，为什么？？就不告诉你，自己想去吧    {        ans+=bit.check(0,cym[i]-1);        bit.updata(cym[i],1);    }    cout<
     
    

区间修改和单点查询的话就是利用数组。

#include
    
     #include
     
      using namespace std;struct node{    int len;    int tree[500100];    node(){len=0;memset(tree,0,sizeof(tree));}    int lowbit(int x)    {        return x&(-x);    }    void updata(int pos,int value)    {        while(pos<=len)        {            tree[pos]+=value;            pos+=lowbit(pos);        }    }    int sum(int pos)    {        if(!pos)            return 0;        int pass=0;        while(pos>0)        {            pass+=tree[pos];            pos-=lowbit(pos);        }        return pass;    }    int check(int left,int right)    {        return sum(right)-sum(left-1);    }};node bit;int main(){    cin.sync_with_stdio(false);    int n,m;    cin>>n>>m;    int a,b,c,d=0;    bit.len=n;    for(int i=1;i<=n;i++)    {        cin>>a;        bit.updata(i,a-d);        d=a;    }    for(int i=1;i<=m;i++)    {        cin>>a;        if(a==1)        {            cin>>b>>c>>d;            bit.updata(b,d);            bit.updata(c+1,-1*d);        }        if(a==2)        {            cin>>b;            cout<
      
       <