树状数组是一个很有用的数据结构，数组内元素的修改和查询区间段元素合是此数据结构的两个基本操作，这里用到两个数组a[],C[]。a数组是原数组，仅用于理解，编码时不用有a数组，基本内容就是用C[]数组来对应原数组a[]，通过对C[] 数组的操作来实现它的两个基本操作：1。修改a中单个元素2。区间求和，的时间复杂度均为O(logN)（根据爱的猥琐大牛的说法，这是第一模式，第二模式为区间段修改，查询单个元素值）
现讨论第一模式：
树状数组用到了二进制的知识：（如图）
也就是说C[N]是a[i]到a[N]的和， N-i + 1= 2^k, k是N的二进制标识形式下末尾0的个数，也可以将2^k看成将N的二进制数减去末尾1时N所减少的数，例如对于12，其二进制1100，2^k = 100B = 2^2。
此时，对于求a到b区间上的和sum（a,b）就可求了，例如sum(3, 7) = getsum(7) – getsum(2);
上面让读者对树状数组可以有个总体直观的印象，下面讨论getsum的实现：
getsum()操作的实现，由前可知就是几个C[]的和，例如getsum(10) = C[10] + C[8] ,又如 getsum(14) = C[14] + C[12] + C[8]等等；下面是实现此操作的代码：
int Getsum(int k)
{
int sum = 0;
while(k>0)
{
sum += c[k];
k -= Lowbit(k);
}
return sum;
}
解释：Lowbit（）是用来求2^k的函数，读者参见上图及解释即可理解
Lowbit（）函数实现：
int Lowbit(int m)
{
return m&(-m);
}
解释：本处用到了位操作，可以自己举几个例子算算加深理解
最后是改变单值的操作了，即对单个元素值的修改，改数时，区间和数组C[]的某些元素就要发生改变，比如对a中第i个数修改，第一步修改C[i]，然后是包含C[i]的直属上级C[j],之后是C[j]的上级C[k]，知道下标超过了数组元素总个数n，就不用再改了，再改没有意义，超过n的范围不会去查询和。下面就是如何由i确定j,再由j确定k的问题了.
对于一个数N，C[N]所包含的数是a[N,i],i = N - 2^k + 1,其上级的可容纳范围必然比它大，而由需要是它直属的上级，最简单的方法就是在N的二进制形式末尾1处再加一，这样这个数的二进制数尾零至少多了一个，而且是它增加尾0最少的方式，就是C[N]的直属上级,可参见上图理解，因此解决这个问题又可以使用到Lowbit函数来求2进制末尾增加1，十进制增加了几；
下面是Change（）函数的代码：
void Change(int k,int m,int n)
{
while(k <= n)
{
c[k] += m;
k += Lowbit(k);
}
}
注：参数是：数组总共有n个元素，将第K个元素加上m。
转自http://jinpingxp.spaces.live.com/blog/cns!56C2A01D2CE133DC!400.entry