Beyond the Void
BYVoid
樹狀數組
本文正體字版由OpenCC轉換

樹狀數組是一個優美小巧的數據結構,在很多時候可以代替線段樹。一句話概括就是,凡是樹狀數組可以解決的問題,線段樹都可以解決,反過來線段樹可以解決的問題,樹狀數組不一定能解決。

樹狀數組英文名稱爲Binary Index Tree,直譯過來就是二進制索引樹,我覺得二進制索引樹更能說明其本質。樹狀數組的本質就是一種通過二進制位來維護一個序列前i和的數據結構。

對於維護的序列A,定義C[i]=A[j+1]+...+A[i],其中ji的二進制表示中把最右邊的1換成0的值。j的值可以通過lowbit求出,即i-lowbit(i)

lowbit(a)2^(a的二進制表示末尾0的個數)。可以用下面式子求出

lowbit(a)=a&(~a+1)

或者根據補碼的性質簡化爲

lowbit(a)=a&(-a)

修改方式如下

	void modify(int p,int delta)
	{
		while (p<=N)
		{
			C[p]+=delta;
			p+=lowbit(p);
		}
	}

求前綴和如下

	int sum(int p)
	{
		int rs=0;
		while (p)
		{
			rs+=C[p];
			p-=lowbit(p);
		}
		return rs;
	}

BYVoid 原創講解,轉載請註明。


上次修改時間 2017-05-22

相關日誌