学步园

        树状数组，我个人理解就是把一个一维的数组，通过转换存在了一个树型的数组里面，从而实现对原数组的快速求和。

        这张图片形象的展示了树状数组的存储结构，

            c[1]=a[1];

            c[2]=a[1]+1[2];

            c[3]=a[3];

            c[4]=a[1]+a[2]+a[3]+a[4];……

        在求和的时候只要对应的求出一些c数组的值就可以求出结果。

        我认为树状数组中最核心的东西是--x&-x,即求x的二进制值中的最低非零位.可以通过这个找到节点的父节点和子节点，

5&-5=1  c[5]的父节点c[6]，6-5=1;这样就可以很快的找到树中节点的关系。因为是用一棵树存储的数组空间，并且每个节

点存的是和所以在求和的时候可以省去每一个节点遍历的时间，时间复杂度更低。

        在树状数组上更新一个节点的时间复杂度是o(logn)，求和的时间复杂度也是o(logn)。至于怎么证明原理是什么，

我也没弄太明白，我个人的理解就是它这样以二进制的方式存储，每次更新是从本节点开始一直更新父节点，对每个父节

点都加上更新的值，然后我猜可能是因为深度是logn吧～～不太懂，菜鸟我的理论就是当定理背下来，哪天想明白了哪天算，

反正目前没有影响。

template <int SZ>
class BIT{
    int c[SZ+10];
    public :
    void clear(){clr(c,0);}
    void update(int x, int n){   //更新
        while(x<=SZ)
            c[x]+=n,x+=x&-x;      //有的人把这个x&-x拿出来单写了
    }
    int getSum(int x){     //求和
        int s=0;
        while(x>0)
            s+=c[x],x-=x&-x;
        return s;
    }
};

ps:招别人抄的代码，自己理解完了自己写的

..............................................................................................华丽的分割线.............................................................................................................................

树状数组：poj    2352   2299    1195    2481    3067    3321    2309    1990    2155      

                    hdu    1556  

        有部分的题要用到离散化，所为离散化就是把比较分散的数据，转换为一段连续的区间内，比如：1  5  9 三个数字比较离散，我们可以

用着 长 这 来对应的表示，从而达到两极差不是很大。

        有的题还会碰到二维的树状数组，就是用一个c[i]表示一个方块内的和，就是一维的一个扩展。

ps:其实算法就是个脑筋急转弯，想明白了，就明白了……