浅学树状数组【持续更新】

树状数组是一种很神奇的数据结构，利用了数的二进制来完成检索的一种兼具高效和代码简洁这俩个特点的树状结构。
他和线段树的区别就在，树状数组能做的线段树都能做，树状数组不能做的线段树也能做（数据范围），但是线段树代码冗长，实现起来没有树状数组简单，在遇到小数据范围时，应该优先考虑树状数组。

树状数组的模样（图片来自黑书）：

在这里我们先介绍一下树状数组的基础操作
1.单点更新

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

代码很简洁，因为树状数组存的是树状结构，x这个值不止在自己的位置出现过，对于每一个x+lowbit(x),都有维护一个对应的x值，因此在更新x的时候，要把所有包含x这个值的tree(node)都要更新，复杂度为O（logn）

2.区间求和

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

这里给出的是计算1-x的区间和，由树状图可知，要求sum，要分块把不同的tree[node]相加得到，对于每一个不同的块，通过x-=lowbit(x)就可以实现
要是要求区间和，只要修改一下参数即可

学会基础操作之后先来一道基础题，poj2182---LOST COWS
题意：有n头牛对应1-n的编号，现在将他们乱序排序，对于第2-n头牛，我们知道在他们之前编号比他们小的牛有几头，现在我们要求出每头牛的编号
这一题数据太水了，有一个 的方法可以直接水过去，这里不做讨论。
对于树状数组我们怎么考虑这一题呢，因为每头牛都只对应唯一的且不同的编号，那么tree[i]就等于lowbit[i],
比如tree[4]=lowbit[4]=4,就代表着编号为1-4的四头牛
由唯一性可知，第n头牛前面有k只编号比他小的牛，那么第n头牛的编号一定为k+1，根据这个条件，我们可以用二分查找去查编号为k+1的牛，并将ans[n]=k+1，处理完第n头牛之后，那么第n-1头牛就变成了最后一个，同理可以确定他的编号，因此我们只要倒着枚举，就可以得出他们所对应的编号，每一次查询完记得删去这个编号即可

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<set>
#include<bitset>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int lowbit(int x){return x&(-x);}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
const int maxn=1e4;

int pre[maxn],ans[maxn],tree[maxn];
int n;
void add(int x,int d)
{
    while(x<=n)
    {
        tree[x]+=d;
        x+=lowbit(x);
    }
}

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

int findpos(int x)
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(sum(mid)<x) l=mid+1;
        else r=mid;
    }
    return l;
}

int main()
{
    n=read();
    rep(i,2,n) pre[i]=read();
    rep(i,1,n) tree[i]=lowbit(i);
    per(i,n,1)
    {
        int pos=findpos(pre[i]+1);
        //printf("%d\n",pos);
        add(pos,-1);
        ans[i]=pos;
    } 
    rep(i,1,n) printf("%d\n",ans[i]);
}