数据结构：树状数组

树状数组

基本操作：1.快速求前缀和 2.修改一个数。

基本图示：

 lowbit：求出一个数字二进制最后一个1的位置；

原理：

我们发现，除了最后一个1，以及其后面的0，其余位置都是反，则要求最后一位1的位置，可以将原码和补码按位&；而计算机中-x有取补码，则lowbit（x）=x&-x；

#define lowbit (x&(-x));

例子：数组：1,2,3,4,5,6,7

1.如果想要修改6=0110, 

则会影响0110对应的：用lowbit+操作就可以修改，即6处修改，6+2（lowbit（6）=2）=8，对8处修改

2.如果想要查询【2,5】之间的和，可以求sum（5）-sum（1）

 sum（5），5=0011，则用lowbit-就可以求出，sum加上5处的值，lowbit（5）=1,5-1=4，sum再加上4处的值，刚好就是sum（5），求出【2,5】，类似于前缀和，求出sum（5）-sum（1）。

综上所述：

1.单点修改

void upload(int x,int d){
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);
    }
}

2.区间查询

int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}

 一个典型题：

我们不难知道，如果想要求解此题，想要知道V（题中）只要知道第个数，左边有个比它大，右边有个比它大，然后就是V的个数,就是总的V图腾数，∧同理（左边，右边比它小）

然后利用树状数组就可以求解逆序对：

lower指比它大的数,Greater比它小的数。

第一遍求左边比它大（小）的数，第二遍（清空第一遍的tr，并逆序求一遍）求右边比它大（小）的数。

注：为啥会求出来，理由是每次更新树状数组， upload(y,1)，则+1，之后遍历下一个数，就知道左边那群数比这个数大还是小的个数是多少（具体例子如下：）

1：for(int i=0;i<n;i++){
        int y=a[i];
        Greater[i]=sum(n)-sum(y);
        lower[i]=sum(y-1);
        upload(y,1);
    }

2： memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i -- )
    {
        int y=a[i];
        res1+=great[i]*(LL)(sum(n)-sum(y));
        res2+=lower[i]*(LL)(sum(y-1));
        upload(y,1);
    }

 左边是第一次，右边是逆序第二次（上面代码1与代码2对应）

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=200010;
int tr[N];
typedef long long LL;
#define lowbit (x&(-x));
int n;
void upload(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int a[N],great[N],lower[N];

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for(int i=1;i<=n;i++){
        int y=a[i];
        great[i]=sum(n)-sum(y);//right
        lower[i]=sum(y-1);//left
        upload(y,1);
    }
    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i -- )
    {
        int y=a[i];
        res1+=great[i]*(LL)(sum(n)-sum(y));
        res2+=lower[i]*(LL)(sum(y-1));
        upload(y,1);
    }
    printf("%lld %lld\n", res1, res2);
    return 0;
}

3.区间修改，单点查询

利用差分数组：

详见差分性质 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr[N];

#define lowbit (x&(-x));

void upload(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
LL sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) upload(i, a[i] - a[i - 1]);

    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if (*op == 'C')
        {
            scanf("%d%d", &r, &d);
            upload(l, d), upload(r + 1, -d);
        }
        else
        {
            printf("%lld\n", sum(l));
        }
    }

    return 0;
}

4.区间修改，区间查询

1.记录差分

   int b = a[i] - a[i - 1];

2.大致思路

如果要求区间修改，利用差分，同上。

但是，区间查询则需要利用一些数学推导：

其中，a为原数组，b为差分数组：

 总面积：，减去黄色部分：，则白色区域：

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和
区间查询：

prefix_sum(r)-prefix_sum(l-1))

区间修改：

 add(tr1, l, d), add(tr2, l, l * d);
 add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);

 总代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和

int lowbit(int x)
{
    return x & -x;
}

void add(LL tr[], int x, LL c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for(int i=1;i<=n;i++){
        int b=a[i]-a[i-1];
        add(tr1,i,b);
        add(tr2,i,(LL)b*i);
    }
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') {
            printf("%lld\n",prefix_sum(r)-prefix_sum(l-1));
        }
        else{
            scanf("%d", &d);
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }
    return 0;
}

5.应用：谜一样的牛

 这个题从正序入手不容易，可以从逆序入手。如何入手，可以举个例子：

 从h【4】=0开始，发现前面没有一个比它低，那么它最低，则是1。然后tree更新。

则发现，只要从最后一个开始，找到第h[i]+1个数就是它的位置，同时更新tree。

为了找到h[i]+1（其实就是求第k小的数，而tr数组记录了数组的前缀和，也就表示了数字到底是在数组中第几小），可以利用二分法。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N=100010;
int n;
int h[N];
int tr[N];
int ans[N];
#define lowbit x&(-x);
void update(int x,int d){
    while(x<=n){
        tr[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)  cin>>h[i];
    for(int i=1;i<=n;i++) update(i,1);
    for(int i=n;i;i--){
        int k=h[i]+1;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(sum(mid)>=k) r=mid;
            else l=mid+1;
        }
        ans[i]=r;
        update(r,-1);
    }
    for (int i = 1; i <= n; i ++ ) printf("%d\n", ans[i]);
    return 0;
}