树状数组小结

树状数组:主要是一维
当然也需要学习二维的树状数组，可以看看二维树状数组
模板：
取数组下标二进制非0最低位所表示的值；
单点更新；
区间查询。
单点更新：
树状数组可以以nlogn的时间复杂度求序列的逆序对；

比如图：
我们要更新c[4]的值，那么，我们只要更新，c[1]及c[3],当c[1]改变那么c[2]也随之改变，如此类推；
c[3],的值；
它们的更新过程，其实是查询过程的逆过程，也就是向下更新，由叶子结点向上更新c[]数组；
sum[4]=A[1]+A[2]+A[3]+A[4]；
int lowbit(int x)//
{
return x&(-x);
}

void update(int x,int val)//更新的值为val
{
for(int j=x;j<=n;j+=lowbit(j))
{
c[j]+=val;
}
}
每次查询是求从查询节点开始（包括查询节点）自右向左层数尽可能低的点的权值的和，算过的点的根节点不再计算（也就是从查询节点开始，从右到左所有需要计算的点的权值和），得到的是前缀和。
每次修改是修改以该点为子节点的所有节点的值。

查询和修改都是以跳跃的形式进行的，时间复杂度都为logn。

比如这个图：
我们进行向上区间查询（求和）
我们进行区间查询（求和）：利用C[i]数组，求A数组中前i项和：
比如：
i=7，前7项和：sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]；
而C[4]=A[1]+A[2]+A[3]+A[4]；
C[6]=A[5]+A[6]；
C[7]=A[7]；
可以得到：sum[7]=C[4]+C[6]+C[7]。
数组下标写成二进制：sum[(111)]=C[(100)]+C[(110)]+C[(111)]；

int lowbit(int x)//
{
    return x&(-x);
}
int sum(int k)//求和
{
    int ans=0;
    for(int i=k;i>0;i-=lowbit(i))
    {
        ans+=c[i];//
    }
    return ans;
}

由于课程关系
简单写了一点理解：
参考文献

可以看道题；
题目链接

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 500010
#define ll long long
int c[MAX];
int num[MAX];
int n;
int lowbit(int x)// **取数组下标二进制非0最低位所表示的值；**
{
    return x&(-x);
}
//void update(int x,int val)//修改
//{
//    while(x<=n){
//        c[x]+=val;
//        x+=lowbit(x);
//    }
//}
//update(a[i],1);
void update(int x)   **单点更新；**
{
    while(x<=MAX)
    {
           c[x]++;//val变为1；
        x+=lowbit(x);
    }
}
void update(int x)//修改
{
    for(int j=x; j<=; j+=lowbit(j))
    {
        c[j]++;
    }
}
int sum(int k)//求和   **区间查询。**
{
    int ans=0;
    for(int i=k; i>0; i-=lowbit(i))
    {
        ans+=c[i];
    }
    return ans;
}
int sum(int x)//节点   求值
{
    int s=0;
    while(x)
    {
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}
bool cmp(node a,node b){//排序
    return a.val<b.val;
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        int x,y;
        memset(c,0,sizeof(c));
        memset(num,0,sizeof(num));
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&x,&y);
            x++;//
            num[sum(x)]++;
            update(x);
        }
        for(int i=0; i<n; i++)
            printf("%d\n",num[i]);
    }
    return 0;
}