算法提高课:树状数组扩展 +差分、+公式
基本原理应用:快速求前缀和修改某一个数分成最多logx个部分,算1-x总和的时候,在加logn个数就可以求出来,复杂度O(logn)2 ^ i1 是x的二进制表示的最后一位1c[x]表示以x为右端点,长度lowbit的区间内所有数的和图中C12应为C9-C12.所有C的关系如图:x> 0, 必然存在最后一位1x = ----- 100…0, 0 y有k个Cx = 以x结尾,长度为2^k的区间和找到x的所有子节点x-1每一次去掉一个最后的1,去地道k次、如何通过子节