
本文共 2246 字,大约阅读时间需要 7 分钟。
先写代码:
第一个函数
int LowBit(int x) //求 最小幂2^k
{ return x & (-x); } 第二个函数
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所表示的数
i | i所对应的二进制 | 2^k(k-->i的二进制的末尾0的个数) |
1 | 01 | 1 |
2 | 10 | 2 |
3 | 11 | 1 |
4 | 100 | 4 |
5 | 101 | 1 |
6 | 110 | 2 |
7 | 111 | 1 |
8 | 1000 | 8 |
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去掉。
由上:
C[i]表示A[i-2^k+1]到A[i]的和,而k则是i在二进制时末尾0的个数。利用位运算,我们可以直接计算出2 ^ k = i & (i ^ (i - 1)) = (i & (-i)),所以C[i]的父节点为C[i + i & (-i)]。
这个k(i的二进制表示末尾0的个数)就是该节点在树中的高度,因而这个树的高度不会超过logn。所以,当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,这个操作的复杂度在最坏情况下就是树的高度即O(logn)。而对于求数列的前n项和S[n],只需找到C[n]以前(包括C[n])的所有最大子树,把其根节点的C[]加起来即可。
不难发现,这些子树的数目是n在二进制表示时1的个数。因此,求和操作的复杂度也是O(logn)。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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关于作者
