本文共 2246 字，大约阅读时间需要 7 分钟。

先写代码：

第一个函数

int getSum(int pos)   //求前n项和{       int sum = 0;       while(pos > 0)       {           sum += arr[pos];           pos -= LowBit(pos);       }       return sum;   }

第三个函数

void update(int pos , int val)   //对某个元素进行加法操作：{       while(pos <= n)       {             arr[pos] += val;             pos += LowBit(pos);       }   }

http://blog.csdn.net/qq_34374664/article/details/52787481    树状数组解释集合

在解题过程中，我们有时需要维护一个数组的前缀和S[n]=A[1]+A[2]+...+A[n]。

          但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。

          可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。

          当n非常大时，程序会运行得非常缓慢。

          因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。

如图所示，红色矩形表示的数组C[]就是我们所维护的树状数组。

该图像的特征：构成了一个以C[8]为根结点，其他C[i]、A[j]为子结点的树。

对于数组A[]下标为奇数时，其上都仅仅只有一个C[]元素，即C[1] = A[1]、C[3] = A[3]、C[5] = A[5]等等

对于数组A[]下标为偶数时，这是一系列A[i]的和。

C[1] = A[1];C[1]的管辖范围为1

C[2] = A[2] + A[1] ;C[2]的管辖范围为2

C[3] = A[3];C[3]的管辖范围为1

C[4] = A[4] + A[3] + A[2] + A[1] ;C[4]的管辖范围为4

C[5] = A[5];C[5]的管辖范围为1

C[6] = A[6] + A[5] ;C[6]的管辖范围为2

C[7] = A[7];C[7]的管辖范围为1

C[8] = A[8] + A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] ;C[8]的管辖范围为8

这里的管辖范围就是说C[]由几个A[]组成。

由上可得(S[]由C[]来表示)：

S[1] = C[1]

S[2] = C[2]

S[3] = C[3] + C[2]

S[4] = C[4]

S[5] = C[5] + C[4]

S[6] = C[6] + C[4]

S[7] = C[7] + C[6] + C[4]

S[8] = C[8]

通过观察图像：S[i]表示为i之前所有最大子树的根结点C[]累加的和

上面所说的管辖范围就是下面列出来的2^k所表示的数

2^k的求法：i 的二进制去掉所有高位的1，只保留最低位的1，如果只存在一个最高位的1，则 2^k 就是它本身。

如1（1），2（10），4（100），8（1000），16（10000）。即都是2的幂。

所以当我们判断一个数x是不是2的次幂时，只要判断x是否等于2^k就可以了，而2^k由位运算很容易求得（x & (-x)）。

对于C[i]如何求得他的父节点？

由上表格推断，C[i]的父节点为C[i+2^k]，也就是说将 i 的二进制的最末尾的1去掉，相邻的高位+1

对于C[i]如何求得他的下一个节点？

由上表格推断，C[i]的下一个节点是C[i-2^k]，也就是说将i的二进制最末尾的1去掉。

由上：

利用位运算，我们可以直接计算出2 ^ k = i & (i ^ (i - 1)) = (i & (-i))，所以C[i]的父节点为C[i + i & (-i)]。

而对于求数列的前n项和S[n]，只需找到C[n]以前（包括C[n]）的所有最大子树，把其根节点的C[]加起来即可。

http://blog.csdn.net/DGY01/article/details/52298912

http://blog.csdn.net/x_iya/article/details/8943264

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

转载地址：https://blog.csdn.net/weixin_38960774/article/details/79405167 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！