有一个数组，第一行是数组下标，第二行是数组中存的值（而且这个数组有实际含义，意思是数字下标出现了的次数用该下标对应的数组的值保存。比如，上面的下标1对应的值是2，意味着1出现了2次）。

对于上面的数组，我们有两种操作：第一，根据下标，改变对应值；第二，求两下标之间所有元素的和。

显然，第一种操作时间是O(1)的。第二种操作时间若是没有第一种操作，可以先把从第一个元素到每一个元素的和存在partial_sum中，然后以后O(1)的时间减一下。但是存在修改操作，如果还是按这种做法，每次修改都要partial_sum.此时，直接计算求和比较方便，但是时间最坏是O(n).

所以，改用一种叫树状数组的结构去存储上面的数组。这时，第一种操作和第二种操作对应的时间都是O(logn)的。

数组下标用2进制表示如上，然后取从低位到高位取第一个非0元素1的位置，前面的1置为0（称为lowest_bit）.如0110转化0010=2，就存当前下标（包括当前下标）的值和前1一个下标对应的值的和（存在lowest_bit个数的和）。对于下标0110就存原数组元素2和1的和（下标分布为5和6）。

求lowest_bit的伪码：

lowest = pos&(-pos)

pos为数组下标。

对于第一种操作，改变某一个下标对应的值，每次只考虑，该下标对应值的增量。这时不仅仅要改变该下标对应的值，也要改变所有包含该下标元素的值。比如0010对应的值由3变为4，增量为1，要改变0010，0100，1000三个位置的值。

while(pos <=n) {

    p[pos] += x;

    pos += lowbit(pos);

}

x为增量，n为数组长度，p是树状数组，pos初始为要改的数组位置的下标。

对于第二种sum操作，求[i,j]的部分和，也是用[1,j]-[1,i-1]来求，求[1,j]的部分和代码，如下所示。

sum=0;

while (pos) {

   sum = p[pos];

   pos -= lowest_bit[pos];

}

讲完了树状数组存的内容和基本操作，下面用两个例子来说明具体应用。

身高排序问题：一个排队买板栗饼的队伍，每个人可以知道在自己前面有多少个人比自己高，求身高由高到低排序。

比如，abcd在排队，a排在最前面，d排在最后面。每个人只知道自己前面有多少个人比自己高，并不知道自己后面有多少个人比自己高。

这个题有一个很直观的解法：d是最后一个人，所有d的身高一定在所有人中排第3.

将d放入正确的位置就可以不用管它了。c一定在剩下的人中排第3，不算d在的位置，数组中的第3个位置就是c的排名。

以此类推，也就是每算一个人的位置，要数一遍数组中没有被填的位置。所有时间是O(n^2)的。

可以用树状数组处理这个问题：

按上面的例子，只有4个人，所有排名只会有1，2，3，4。初始时没有确定排名，每一个名次出现的人数上限都是1。

为了示意，我把真实数组和partial_sum和数状数组都表示出来了，但是真实做的时候，只用存树状数组就好。

因为d,一定排在第三个，对数组下标二分，此时为数组下标为2，由sum操作求[1,2]区间和，为2，小于3.下次数组下标就为3，此时[1,3]的区间和恰好为3，就找到了d的位置。二分log(n)时间，求区间和log(n)时间，所以把一个人放到正确的排名处就是log(n)*log(n)时间。

把d排好后，要用log(n)改树状数组。

第三名位置被占，不能放值，置为0.按同样的方法放剩下的每一个元素，n个元素，所以时间复杂度就降为了O(n*log(n)*log(n))时间。

连续部分和在某区间的个数问题：

//连续部分和代码

class NumArray {

public:

   NumArray(vector<int> &nums)  {

       _tree.resize(nums.size()+1, 0); // 下标是从1开始的

       for (int i=0; i< nums.size(); ++i) {

           update(i, nums[i]);

       }

   }

   void update(int i, int val) {

      //要查出来i原来的值是多少，可以用减法，也可以用空间存起来

       int add = val - (sum(i+1)-sum(i));

       i += 1;   //跟新下表要从1开始

       while (i<_tree.size()) {

           _tree[i] += add;

           i += lowbit(i);

       }

   }

   int lowbit(int k) {

       return k&(-k);

   }

   int sum(int k) {

       int sum = 0;

       while (k) {

           sum += _tree[k];

           k -= lowbit(k);

       }

       return sum;

   }

   int sumRange(int i, int j) {

       return sum(j+1) - sum(i); // 包括i和j

   }

   private:

   vector<int> _tree;

};

参考文献：

http://blog.csdn.net/int64ago/article/details/7429868

这个blog把树状数组为什么可以这样实现说得很清楚。