lowbit()

創(chuàng)新互聯(lián)公司主營二連浩特網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,APP應(yīng)用開發(fā),二連浩特h5小程序開發(fā)搭建,二連浩特網(wǎng)站營銷推廣歡迎二連浩特等地區(qū)企業(yè)咨詢

lowbit(x)是x的二進(jìn)制表達(dá)式中最低位的1所對應(yīng)的值（即返回x二進(jìn)制為一的最低位數(shù)值）。

lowbit(0)=0

常用寫法：

int lowbit(int x){
	return x&(-x);
}
//利用了負(fù)整數(shù)的補(bǔ)碼特性

用法

維護(hù)區(qū)間

設(shè)節(jié)點編號為x，那么該節(jié)點維護(hù)的區(qū)間和是 $ ( x - lowbit ( x ) , x ] $ 。

樹狀數(shù)組

基本操作復(fù)雜度： $ O ( logn ) $

樹狀數(shù)組利用了lowbit()來進(jìn)行區(qū)間維護(hù)。

令父節(jié)點儲存其子節(jié)點之和，

則不難發(fā)現(xiàn)：

$ C [ i ] = A [ i - 2k + 1 ] + A [ i - 2k + 2 ] + ...... A [ i ] $

（k為i的二進(jìn)制中從最低位到高位連續(xù)零的長度）

lowbit(x) 就是取出x的最低位1,換言之lowbit(x)=2k, k的含義與上面相同,所以：

$ C [ i ] = A [ i - lowbit ( i ) + 1 ] + A [ i - lowbit ( i ) + 2 ] + ...... A [ i ] $

主要性質(zhì)

性質(zhì)1

每個內(nèi)部結(jié)點 $ C [ x ] $ 保存以它為根的子樹中所有葉結(jié)點的和。

應(yīng)用

前綴和查詢

區(qū)間和查詢

$ sum ( y ) - sum ( x - 1 ) $

性質(zhì)2

每個內(nèi)部結(jié)點 $ C [ x ] $ 的子結(jié)點個數(shù)等于其lowbit(x)的值。

性質(zhì)3

除樹根以外，每個內(nèi)部結(jié)點 $ C [ x ] $ 的父親結(jié)點是 $ C [ x + lowbit ( x ) ] $

應(yīng)用

單點修改

性質(zhì)4

樹的深度為 $ O ( logn ) $ 。

注意

樹狀數(shù)組只能處理下標(biāo)為1...n的數(shù)組，絕不能出現(xiàn)下標(biāo)為0的情況。因為lowbit(0)=0，會陷入死循環(huán)。

拓展

一維樹狀數(shù)組的每個操作都是 $ O ( logn ) $ ，它可擴(kuò)展到m維,復(fù)雜度變成 $ O ( log^m n ) $

擴(kuò)展方法

將原來的修改和查詢函數(shù)中的一個循環(huán)，改成m個循環(huán)（m維數(shù)組c中的操作），以二維為例：

并非原創(chuàng)，僅是整理，請見諒