树状数组简单易懂的详解,数组转树结构

树状数组解决的问题：

假如有这样一种情景，先输入一个长度为n的数组，然后我们有如下两种操作：

输入一个数m，输出数组中下标1~m的前缀和对某个指定下标的数进行值的修改

多次执行上述两种操作；

常规方法

对于一个的数组，如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和，对于值的修改，我们可以直接通过下标找到要修改的数，然后更新前缀和，对于一次操作显然没什么问题，但对于 n n n次操作，时间复杂度就达到了 O ( n 2 ) O(n^2) O(n2)和 O ( n ) O(n) O(n)，这样的方法就显得不适用了。

树状数组

如图，对于一个长度为n的数组，A数组存放的是数组的初始值，引入一个辅助数组C；

C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

我们称C[i]的值为下标为i的数所管辖的数的和，下标为i的数所管辖的元素的个数为 2 k 2^k 2k个（k为i的二进制的末尾0的个数），例如：

i = 8 = 1000，末尾3个0，故k = 3，所管辖的个数为 2 3 = 8 2^3 = 8 23=8，C8是8个数的和；i = 5 = 0101，末尾没有0，故k = 0，所管辖的个数为 2 0 = 1 2^0 = 1 20=1，C5是一个数的和；

而对于输入的数m，我们要求编号为m的数的前缀和 A 1 ⋯ A m A_1cdots A_m A1​⋯Am​，按照上面说的， s u m m = C i 1 + C i 2 + ⋯ sum_m= C_{i_1} + C_{i_2} + cdots summ​=Ci1​​+Ci2​​+⋯，这里m和C[i]的对应关系是这样的，对于查询的m，将它转换成二进制后，不断对末尾的1的位置进行-1的操作，直到全部为0停止，中间得到的值就是c[i]，例如：

m = 7， s u m 7 = C 7 + C 6 + C 4 sum_7 = C_7 + C_6 + C_4 sum7​=C7​+C6​+C4​，7的二进制为0111（ C 7 C_7 C7​得到），对0111的末尾1的位置-1，得到0110 = 6（ C 6 C_6 C6​得到），再对0110末尾1位置-1，得到0100 = 4（ C 4 C_4 C4​得到），最后对0100末尾1位置-1后得到0000（结束），计算停止，至此 C 7 ， C 6 ， C 4 C_7，C_6，C_4 C7​，C6​，C4​全部得到，求和后就是m = 7时它的前缀和；m = 6， s u m 6 = C 6 + C 4 sum_6 = C_6 + C_4 sum6​=C6​+C4​，6的2进制等于·0110·，经过两次变换后为0100（C4）和0000（结束信号），那么求和后同样也得到了预计的结果；

那么求前缀和的代码如下：

int lowbit(int m){ return m & (-m);}int getSum(int m){int ans = 0; while(m > 0){ ans += C[m]; m -= lowbit(m); } return ans;}

关于m & (-m)这是一个很巧妙的地方，如13的二进制表示为1101，那么-13的二进制表示为0010 + 0001 = 0011，那么1101 & 0011 = 0001，二进制末尾1的位置是 2 0 2^0 20，将13 - 0001 = 12，再对12执行lowbit操作，1100 & 0100 = 0100，二进制末尾1的位置是 2 2 2^2 22，将12 - 0100 = 8，再对8执行lowbit操作，0100 & 1100 = 0100，二进制位是 2 2 2^2 22，8 - 0100 = 0（结束操作），通过循环得到的13，12，8，则 s u m 13 = C 13 + C 12 + C 8 sum_{13} = C_{13} + C_{12} + C_8 sum13​=C13​+C12​+C8​.

建立树状数组

对于一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程，所以建树与单点更新值是一样的，即把 A 1 ⋯ A n A_1cdots A_n A1​⋯An​从0更新成我们输入的A[i]，所以一边读入A[i]，一边将C[i]涉及到的祖先节点值更新，完成输入后树状数组C也就建立成功了。

下面说说如何更新节点值：

假设更新A[2] = 5，通过观察我们得知，如果修改了A[2]的值，那么管辖A[2]的C[2]，C[4]，C[8]的前缀和都要加上5（所有的祖先节点），那么和查询类似，我们如何得到C2的所有祖先节点呢，依旧是上述的巧妙的方法，但是我们把它倒过来用，对于要更新i位置的值，我们把i转换成二进制，不断对二进制最后一个1的位置+1，直到达到数组下标的最大值n结束，对于给出的例子i = 2，假设数组下标上限n = 8，i转换成二进制后等于0010（ C 2 C_2 C2​），对末尾1的位置进行+1，得到0100（ C 4 C_4 C4​），对末尾的1的位置进行+1，得到1000（ C 8 C_8 C8​），循环结束，对 C 2 ， C 4 ， C 8 C_2，C_4，C_8 C2​，C4​，C8​的前缀和都要+5，当然不能忘记对A[2]的值+5，单点更新值过程结束。

void update(int x, int value){ A[x] += value;// 修改源数组 while(x <= n){ C[x] += value; x += lowbit(x); }} 完整代码 #include<stdio.h>#include<string.h>int a[10005];int c[10005];int n;int lowbit(int x){ return x&(-x);}int getSum(int x){ int ans = 0; while(x > 0){ ans += c[x]; x -= lowbit(x); } return ans;}void update(int x, int value){ a[x] += value; while(x <= n){ c[x] += value; x += lowbit(x); }}int main(){ while(scanf("%d", &n)!=EOF){ memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); update(i, a[i]); } int ans = getSum(n-1); printf("%dn", ans); } return 0;}

参考：https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html