透彻理解树状数组

附上树状数组的讲解：

修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！

当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是O(M*lgN)，别小看这个lg，很大的数一lg就很小了

a数组就是我们要维护和查询的数组，但是其实我们整个过程中根本用不到a数组，你可以把它当作一个摆设！c数组才是我们全程关心和操纵的重心。先由图来看看c数组的规则，其中c8 = c4+c6+c7+a8，c6 = c5+a6……先不必纠结怎么做到的，我们只要知道c数组的大致规则即可，很容易知道c8表示a1～a8的和，但是c6却是表示a5～a6的和，为什么会产生这样的区别的呢？或者说发明她的人为什么这样区别对待呢？答案是，这样会使操作更简单！

lowbit(k)就是把k的二进制的高位1全部清空，只留下最低位的1,比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制)，介于这个lowbit在下面会经常用到，这里给一个非常方便的实现方式，比较普遍的方法lowbit(k)=k&-k，这是位运算，我们知道一个数加一个负号是把这个数的二进制取反+1，如-10的二进制就是-1010=0101+1=0110，然后用1010&0110，答案就是0010了！明白了求解lowbit的方法就可以了，继续下面。介于下面讨论十进制已经没有意义（这个世界本来就是二进制的，人非要主观的构建一个十进制），下面所有的数没有特别说明都当作二进制。

上面那么多文字说lowbit，还没说它的用处呢，它就是为了联系a数组和c数组的！ck表示从ak开始往左连续求lowbit(k)个数的和，比如c[0110]=a[0110]+a[0101]，就是从110开始计算了0010个数的和，因为lowbit(0110)=0010，可以看到其实只有低位的1起作用，因为很显然可以写出c[0010]=a[0010]+a[0001]，这就为什么我们任何数都只关心它的lowbit，因为高位不起作用（基于我们的二分规则它必须如此！），除非除了高位其余位都是0，这时本身就是lowbit。

 

木桩涂涂看

通过这个题彻底理解了树状数组，其实getsum(i)就是最后i这个位置的值是多少，树状数组只不过是对区间操作进行了一次加强，使得不使用o(n)的时间，最后时间节省为o(lgn)，刚开始理解老是觉得getsum(i)就是将所有之前的全部加起来，其实人家有个lowbit操作就很神奇，并非所想的那样。使用其实很简单，板子放main上面，下面就套用就想成一般的，只不过最后人家对应的是getsum(i)是最后这个位置上的值。

//透彻理解树状数组中的getsum到底是啥
#include<iostream>
#include<cstdio>

using namespace std;

const int maxn=1e5;

int tree[maxn];

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

void change(int t,int v)
{
    for(;t<=maxn;t+=lowbit(t)){
        tree[t]+=v;
    }
}
int getsum(int t)
{
    int res=0;
    for(;t;t-=lowbit(t)){
        res+=tree[t];
    }
    return res;
}

int main()
{
    int n;
    scanf("%d",&n);
    int a,b;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        change(a,1);
        change(b+1,-1);
    }
    for(int i=1;i<=n;i++){
        if(i!=1){
            printf(" ");
        }
        printf("%d",getsum(i));
    }
    return 0;
}

还有一种使用线段树Lazy操作

//线段树Lazy操作
#include<iostream>
#include<cstdio>

using namespace std;

typedef long long LL;

const int maxn=1e5+100;

struct node{
    LL l,r,sum;
};
node tree[maxn<<2];
LL lazy[maxn<<2];
LL a[maxn];

lazy核心操作
void push_down(LL p)
{
    lazy[p<<1]+=lazy[p];
    lazy[p<<1|1]+=lazy[p];
    tree[p].sum+=(tree[p].r-tree[p].l+1)*lazy[p];
    lazy[p]=0;
}

void build(LL p,LL l,LL r)
{
    tree[p].l=l;
    tree[p].r=r;
    tree[p].sum=0;
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void update(LL p,LL l,LL r,LL v)
{
    if(tree[p].l==l&&tree[p].r==r){
        lazy[p]+=v;
        return ;
    }
    tree[p].sum+=(r-l+1)*v;
    if(lazy[p]!=0){
        push_down(p);
    }
    LL mid=(tree[p].l+tree[p].r)>>1;
    if(r<=mid){
        update(p<<1,l,r,v);
    }else if(l>mid){
        update(p<<1|1,l,r,v);
    }else{
        update(p<<1,l,mid,v);
        update(p<<1|1,mid+1,r,v);
    }
}

LL find(LL p,LL l,LL r)
{
    if(tree[p].l==l&&tree[p].r==r){
        return tree[p].sum+(r-l+1)*lazy[p];
    }
    if(lazy[p]!=0){
        push_down(p);
    }
    LL mid=(tree[p].l+tree[p].r)>>1;
    if(r<=mid){
        return find(p<<1,l,r);
    }else if(l>mid){
        return find(p<<1|1,l,r);
    }else{
        return find(p<<1,l,mid)+find(p<<1|1,mid+1,r);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    build(1,1,n);
    int x,y;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        update(1,x,y,1);
    }
    for(int i=1;i<=n;i++){
        if(i!=1){
            printf(" ");
        }
        printf("%lld",find(1,i,i));
    }
    printf("\n");
    return 0;
}