權值線段樹 基礎入門知識詳解

權值線段樹

• 學習權值線段樹，首先要了解線段樹是什麼。如果不會的可以先學習一下。

是什麼

• 權值線段樹，顧名思義是一棵線段樹。
• 但它和普通線段樹不同：
• 線段樹，每個節點用來維護一段區間的最大值或總和等。
• 權值線段樹，相當于一個桶，每個節點用來表示一個區間的數出現的次數。

為什麼要用它

• 我們可以用它來維護一段區間的數出現的次數，從它的定義上來看，它可以快速計算一段區間的數的出現次數。

• 此外，它還有一個重要功能，在于它可以快速找到第 k k k大或第 k k k小值，下面會做詳細解釋。

  其實，它就是一個桶，桶能做到的它都可以用更快的速度去完成。

基本操作

添加

• 和普通線段樹類似，遞歸到葉子節點時給 f [ v ] + 1 f[v]+1 f[v]+1。
• 以下代碼要添加的數是 x x x，也就是 x x x出現的次數 + 1 +1 +1。

void add(int l,int r,int v,int x)
	{
		if(l==r) f[v]++;
		else
		{
			int mid=(l+r)/2;
			if(x<=mid) add(l,mid,v*2,x); else add(mid+1,r,v*2+1,x);
			f[v]=f[v*2]+f[v*2+1];
		{
	}
           

查詢一個數出現的次數

• 如添加操作，遞歸到葉子節點時 f [ v ] f[v] f[v]的值即為所求次數。
• 以下代碼要查詢的數是 x x x。

int find(int l,int r,int v,int x)
	{
		if(l==r) return f[v];
		else
		{
			int mid=(l+r)/2;
			if(x<=mid) return find(l,mid,v*2,x); else return find(mid+1,r,v*2+1,x);
		}
	}
           

查詢一段區間的數出現的次數

• 與線段樹查詢同理，不斷遞歸二分。
• 以下代碼要查詢的區間是 [ x , y ] [x,y] [x,y]。

int find(int l,int r,int v,int x,int y)
	{
		if(l==x&&r==y) return f[v];
		else
		{
			int mid=(l+r)/2;
			if(y<=mid) return find(l,mid,v*2,x,y);
			else if(x>mid) return find(mid+1,r,v*2+1,x,y);
			else return find(l,mid,v*2,x,mid)+find(mid+1,r,v*2+1,mid+1,y);
		}
	}
           

查詢所有數的第k大值

• 這是權值線段樹的核心，思想如下：
• 到每個節點時，如果右子樹的總和大于等于 k k k，說明第 k k k大值出現在右子樹中，則遞歸進右子樹；否則說明此時的第 k k k大值在左子樹中，則遞歸進左子樹，注意：此時要将 k k k的值減去右子樹的總和。
• 為什麼要減去？
• 如果我們要找的是第 7 7 7大值，右子樹總和為 4 4 4， 7 − 4 = 3 7-4=3 7−4=3，說明在該節點的第 7 7 7大值在左子樹中是第 3 3 3大值。
• 最後一直遞歸到隻有一個數時，那個數就是答案。

int kth(int l,int r,int v,int k)
	{
		if(l==r) return l;
		else
		{
			int mid=(l+r)/2,s1=f[v*2],s2=f[v*2+1];
			if(k<=s2) return kth(mid+1,r,v*2+1,k); else return kth(l,mid,v*2,k-s2);
		}
	}
           

總結

• 權值線段樹的基礎知識就是這些了，相信你都學會了。
• 希望你能夠靈活變通，在今後的OI生涯中更上一層樓。
• 如果你想學習進階知識，可以看看【主席樹】可持久化線段樹