189 8069 5689
lowbit()
创新互联公司主营二连浩特网站建设的网络公司,主营网站建设方案,APP应用开发,二连浩特h5小程序开发搭建,二连浩特网站营销推广欢迎二连浩特等地区企业咨询
lowbit(x)是x的二进制表达式中最低位的1所对应的值（即返回x二进制为一的最低位数值）。
lowbit(0)=0
常用写法：
int lowbit(int x){
return x&(-x);
}
//利用了负整数的补码特性
用法
维护区间
设节点编号为x，那么该节点维护的区间和是 $ ( x - lowbit ( x ) , x ] $ 。
树状数组
基本操作复杂度： $ O ( logn ) $
树状数组利用了lowbit()来进行区间维护。
令父节点储存其子节点之和，
则不难发现：
$ C [ i ] = A [ i - 2k + 1 ] + A [ i - 2k + 2 ] + ...... A [ i ] $
（k为i的二进制中从最低位到高位连续零的长度）
lowbit(x) 就是取出x的最低位1,换言之lowbit(x)=2k, k的含义与上面相同,所以：
$ C [ i ] = A [ i - lowbit ( i ) + 1 ] + A [ i - lowbit ( i ) + 2 ] + ...... A [ i ] $
主要性质
性质1
每个内部结点 $ C [ x ] $ 保存以它为根的子树中所有叶结点的和。
应用
前缀和查询
区间和查询
$ sum ( y ) - sum ( x - 1 ) $
性质2
每个内部结点 $ C [ x ] $ 的子结点个数等于其lowbit(x)的值。
性质3
除树根以外，每个内部结点 $ C [ x ] $ 的父亲结点是 $ C [ x + lowbit ( x ) ] $
应用
单点修改
性质4
树的深度为 $ O ( logn ) $ 。
注意
树状数组只能处理下标为1...n的数组，绝不能出现下标为0的情况。因为lowbit(0)=0，会陷入死循环。
拓展
一维树状数组的每个操作都是 $ O ( logn ) $ ，它可扩展到m维,复杂度变成 $ O ( log^m n ) $
扩展方法
将原来的修改和查询函数中的一个循环，改成m个循环（m维数组c中的操作），以二维为例：
并非原创，仅是整理，请见谅