树状数组学习笔记
约定：C是树状数组，A是原数组，下面以索引 i 为示例进行讲解 设计目的：解决区间查询、前缀求和中数组每项之间强依赖、降低数组中每项和其它项的关联，查询和修改时间复杂度达到O(logN)。 方法：采用lowbit来达到稀疏目的(这个说法不知道是否准确)。 lowbit定义：索引数值按照二进制展开，末尾零的个数的2次幂，比如1100末尾有2个零，则lowbit=2^2=4，0011末尾有0个零，则lowbit=2^0=1，可以看出，奇数末尾都是0个零，所以奇数lowbit都是1。 lowbit意义：表征数组每个元素所在的索引求和所管辖覆盖的范围，比如lowbit(4)=4，则表示第4个元素的数组元素C(4)=A(4)+A(3)+A(2)+A(1)，即包含本身总共是4个元素的和。lowbit(6)=2，则表示第6个元素的数组元素C(6)=A(6)+A(5)，即包含本身总共是2个元素的和。如下图所示(窃取船长专利图)： 
文章图片
每个元素所管辖的范围是lowbit(i)，数组索引区间范围：[i-(lowbit(i)-1)，i]，即从本身位置往前移动（lowbit(i)-1）个元素，为何要减1？因为要排除本身啊，包含本身元素才有lowbit(i)个，那本身前面不就是少1个了。 每个元素上面最近的管辖自己的元素索引是：i+lowbit(i)，为什么？ 当前索引i我们按照奇偶性进行分析： a、i是奇数 根据上面lowbit的定义，i是奇数时下一个元素一定是偶数，而偶数的lowbit一定>=2，这就说明下一个元素一定覆盖i元素，所以下一个元素就是i+1，而奇数时lowbit(奇数)=1，所以下一个元素的索引 j=i+lowbit(i)。 b、i是偶数 由于i是偶数，说明i后面的元素一定是奇数，而奇数的lowbit为1，不可能覆盖i元素，所以后移一位不可行，那么要后移几位才可以覆盖到本元素呢？ 我们从下面的示意图可以看出来，i元素要能够被后面的元素覆盖，那么管辖范围的值就必须比i所在的管辖范围值大，那大多少呢？从下图可以看出，实际就是大一倍，也就是直接上一层，那么现在问题就变成距离i最近的上层索引怎么计算得到。 从下图还可以看出，lowbit越大，管辖范围越大，所处层次越高，所以i后面的元素要能够覆盖i，则后面元素的lowbit必须比i的lowbit大，而lowbit的值的大小和值后面的零的个数是2的幂次方的关系，所以要比当前i的lowbit大，要保证零的个数比lowbit(i)多，那满足最小条件的个数就是比原来多1个零，而这个操作可以通过左移一位lowbit(i)得到，而这个操作的结果就是i+lowbit(i)。 如果对这个公式还不理解，那再换另一种思路：我们从i后面一个元素一个元素查找满足覆盖i元素的条件的元素，我们发现从 i+1 到 i+(lowbit(i)-1) 这个范围的结果都不满足新索引值的lowbit值比i的lowbit值大，一直到 i+lowbit(i)，由于i的最右部分就是lowbit(i)，所以i+lowbit(i)相当于最右部分两个lowbit相加，那么两个最高位1相加就产生进位，这时新值的最右部分的零就比原来lowbit(i)多一个了，也就满足了覆盖i元素的新索引值的要求。 实际上i是奇数和偶数都可以很好的用上述方式解释，只是奇数方式的原理更容易懂。 现在还有一个问题：我们按照这种方式查找会不会遗漏？ 因为使用路径 i->i+lowbit(i)->i+lowbit(i)+lowbit(i+lowbit(i)) 查找，这种方式是有索引跨度的，会不会发生i上层的某层元素被遗漏了的情况？其实这个是不会的，为什么？因为树状数组就是树形结构的简单体，层次关系和树形结构一致，不会发生某个元素的父元素的父元素不是自己祖先的情况，也不会遗漏，因为我们从子节点查找所有的父节点都是一层一层往上查找，不会跳过任何父节点。 可以参照如下示例理解： 【树状数组学习笔记】 
文章图片
文章图片
推荐阅读
- 由浅入深理解AOP
- 继续努力，自主学习家庭Day135(20181015）
- python学习之|python学习之 实现QQ自动发送消息
- 一起来学习C语言的字符串转换函数
- 定制一套英文学习方案
- 漫画初学者如何学习漫画背景的透视画法（这篇教程请收藏好了！）
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 如何更好的去学习
- 【韩语学习】（韩语随堂笔记整理）
- 数组常用方法一