這篇文章介紹了樹狀數組及其基本應用。

數據結構1——聊聊樹狀數組的那些事

目錄

Part1.那些樹狀數組能解決的問題

Part2.lowbit

Part3.初識樹狀數組

Part4.樹狀數組的性質

Part5.樹狀數組與區間查詢

Part6.樹狀數組與單點修改

Part7.樹狀數組與建樹

Part8.樹狀數組與逆序對

Part9.權值樹狀數組與動態第k小

Part01:那些樹狀數組能解決的問題

樹狀數組能解決區間修改單點查詢，單點修改區間查詢，動態第 \(k\) 小的數，逆序對等問題。

有時，在差分數組和輔助數組的幫助下，樹狀數組還可解決更強的區間加單點值和區間加區間和問題。

樹狀數組可以解決的問題，線段樹也一定能解決。但是線段樹能解決的問題，樹狀數組不一定能解決。

但是，線段樹和樹狀數組能共同解決的問題中，樹狀數組的效率更高，且碼量更小，可以節約一點比賽時的時間和評測所用的時間。

所以，樹狀數組也具有一定的價值，值得我們學習。

（線段樹是數據結構2的內容）

Part02:lowbit

在很久以前我們學習過二進制。我們知道，\(\text{lowbit}(x)\)，表示一個數的二進制從后往前數第一個 \(1\) 及其右邊的 \(0\) 所構成的二進制的數（如 \((1000000000)_2\)）所代表的十進制值。

那 \(\text{lowbit}\) 怎么簡便求出呢？

設一個二進制數 \(x\) 的最低位 \(1\) 是第 \(k\) 位，則它的 \(0\to k-1\) 位都是 \(0\)。

那么此時，\(-x\)，即 \(\text{~}x+1\)，也即 \(x\) 取反再 \(+1\)，會把 \(k+1\) 到最高位全部取反，但因為 \(0\to k-1\) 位都是 \(0\)，取反后均變為 \(1\)，然后由于 \(+1\)，又全部變為 \(0\)，進位到第 \(k\) 位，而第 \(k\) 位又取反變為 \(0\)，加上進位 \(1\) 正好又變為 \(1\)，與原來的數一做與運算，就可以把 \(k+1\) 位到最高位全部消掉，就剩下 \(0\to k\) 位，也即 \(\text{lowbit(x)}\) 了。

所以 \(\text{lowbit(x)}=x\text{&}-x\)。

實現：

int lowbit(int a)
{
	return a&(-a);
}

Part03:初識樹狀數組

在很久以前，我們曾學習過前綴和。它能讓我們快速得到一個區間的和。但是預處理它太慢了，而且一旦是動態數組，那前綴和的效率就會銳減。這時，樹狀數組登場了。

我們可以假設，我們需要求 \(a_1\) 到 \(a_7\) 的和。用前綴和的話，我們只能用 \(a_1+a_2+a_3+a_4+a_5+a_6+a_7\)。但是，如果有三個變量 \(A=a_1+a_2+a_3+a_4,B=a_5+a_6,C=a_7\)，那么， \(a_1\) 到 \(a_7\) 的和就變成了 \(A+B+C\)，十分方便。

我們將一段前綴拆成不多于 \(\log n\) 個的區間，那么這 \(\log n\) 段區間的信息（和、積等）就變成了已知的。

那如何求這 \(\log n\) 個區間呢？

如下圖，這就是一個樹狀數組。

我們可以發現，在這個樹狀數組中，\(c_1\) 管轄的是 \(a_1\)，\(c_2\) 管轄的是 \(c_1\) 和 \(c_2\)，\(c_3\) 管轄的是 \(a_3\)，\(c_4\) 管轄的是 \(c_2,c_3\) 和 \(a_4\)…

這時，當我們想要計算 \(a_1\) 到 \(a_7\) 的和，可以按照如下步驟：

先看 \(c_7\)，發現 \(c_7\) 管轄 \(a_7\)，然后看 \(c_{7-1=6}\)，發現 \(c_6\) 管轄 \(a_5,a_6\)，然后看 \(c_{5-1=4}\)，發現 \(c_4\) 管轄 \(a_1,a_2,a_3,a_4\)，然后看 \(c_{1-1=0}\)，發現 \(c_0\) 不存在，步驟結束。

我們看的三個數 \(c_7,c_6,c_4\) 加起來就是 \(a_1\) 到 \(a_7\) 的和。

Part04:樹狀數組的性質

樹狀數組具有如下性質：

1.每一個 \(c\) 數組的元素都管轄了以它為根的子樹里的與元素之和。

2.每個節點的父親節點都是（設下標為 \(x\) 且除根結點） \(x+\text{lowbit(x)}\)。

3.\(\text{lowbit(x)}\) 即為以 \(x\) 為根的子樹的葉子結點個數。

Part05:樹狀數組與區間查詢

根據樹狀數組的性質 \(3\)，設我們要查 \(a_1\) 到 \(a_x\) 的和，可以不斷地先把答案加上 \(c_x\)，再將 \(x-\text{lowbit}(x)\) 直到 \(x=0\) 來得到答案。

實現：

int ret(int x)
{
	int ans=0;
	while(x>0)
	{
		ans+=c[x];
		x-=lowbit(x);
	}
	return ans;
}

Part06:樹狀數組與單點修改

需要用到樹狀數組的題，一般都是動態的，這時我們就需要修改。

根據樹狀數組的性質 \(2\)，當我們將一個數（設其下標為 \(x\)）加上 \(y\) 時，我們需要把 \(c_x\) 的父親節點都加上 \(y\)，這就是單點修改。

實現：

void add(int x,int y)
{
	while(x<=n)
	{
		c[x]+=y;
		x+=lowbit(x);
	}
}

減 \(y\) 乘 \(y\) 除 \(y\) 等都能解決，萬能法寶。

Part07:樹狀數組與建樹

初學樹狀數組，我們可以用時間復雜度 \(O(n\log n)\) 的建樹算法。

建樹，其實可以轉化為 \(n\) 次單點修改。

即對于一個下標為 \(i\) 的數 \(a_i\)，使用單點修改的 \(\text{add}\) 函數，\(\text{add}(i,a_i)\) 就能建樹了。

實現：

void build(int l,int r)
{
	for(int i=l;i<=r;i++)
	{
		add(i,a[i]);
	}
}

Part08:樹狀數組與逆序對

逆序對怎么用樹狀數組求呢？

可以對于 \(1\) 到 \(n\)，求出 \(1\to a_i\) 的和，用答案加上這個值后，單點修改 \(i\)（加上 \(a_i\)）。

Part09:權值樹狀數組與動態第k小

權值線段樹（數據結構2內容）有了，怎么能沒有權值樹狀數組呢？

它們一般都是用來解決第k小的問題的。

那么怎么做呢？

考慮倍增（提高組算法詳解7內容）。

設 \(x=0\)，\(sum=0\)，枚舉 \(i\) 從 \(\log_2n\) 降為 \(0\)：

• 查詢權值數組中 \(x+1\to x+2^i\) 的區間和 \(t\)。
• 如果 \(sum+t<k\)，擴展成功，\(x=x+2^i\)，\(sum=sum+t\)；否則擴展失敗，不操作。

這樣得到的 \(x\) 滿足 \(1\to x\) 前綴和 \(<k\) 的最大值，所以最終 \(x+1\) 就是答案。

當然也可以用并查集來解決。

代碼：

int slove(int k)
{
	int sum=0,x=0;
	for(int i=log2(n);i>=0;--i)
	{
		x+=1<<i;
		if(x>= n||sum+t[x]>=k)
		{
			x-=1<<i;
		}
		else
		{
			sum+=t[x];
		}
	}
	return x+1;
}

至此，數據結構1就結束了。