天天看點
傳回

進化版資料結構（可持久化）·線段樹給你個問題：要怎麼做？【面面相觑】Code：·帶修主席樹·Trie

·線段樹

主席樹和可持久化線段樹有什麼差別？

主席樹（可持久化線段樹）

可持久化線段樹（Persistent data structure）最主要的功能就是可以查詢曆史版本。那麼presistent≈president（主席），得名主席樹。

給你個問題：

給你一段數列，要求查詢一段區間的第k小數。\((n<=10^5)\)

要怎麼做？【面面相觑】

很容易想到兩種方法：

①建一棵線段樹，然後再每個表示區間的節點上都建一棵權值線段樹！直接查詢即可。

②建n棵線段樹，第i棵線段樹表示1~i裡面所有的數構成的權值線段樹！那麼查詢區間的時候就直接像使用字首和一樣，每個節點表示的權值區間在這個查詢的區間中擁有數的個數就是：目前節點個數減去區間左端點建的樹中對應的點的數量。

例如：

我們查詢區間[2~4]的第k小，我們可以很顯然的地得出：每個節點的值其實就是在第4棵線段樹上這個節點的值減去在第一棵線段樹上這個節點的值。然後按照權值線段樹的查詢規律下去找就好了。

很明顯這個算法的時間空間複雜度都是\(O(n^2\) \(log\) \(n)\)的。

主席樹的主體是線段樹，準确的說，是很多棵線段樹。那麼如何既能建出那麼多棵線段樹，同時不會MLE、TLE.

很顯然我們會發現，修改字首和的時候隻有可能加入一個數，而受到這個數影響的隻有可能有一條鍊，那麼其他我們新開的點就都是廢的了。我們每次隻需要建立這條鍊，把其他跟上次一樣的東西繼承過來就好了，被繼承的點就叫做共用！當然一個點有可能會被多個點共用！這樣的話我們就可以将空間和時間複雜度大大減小。

圖如下：

對照上圖，節點内的數字表示以該點為根的字數擁有的數字個數。這樣空間省去很多，每次隻會增加一條鍊，那麼空間複雜度就是\(O(n log n+n log n)\),時間複雜度和普通線段樹一樣，都是每次操作隻有\(O(log n)\)的時間。

Code： 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct Moon{
	int rs,ls,num;
}tree[4000010];
struct Candy{
	int x,y;
}a[200010],b[200010];
int root[200010],c[200010];
int n,m,sz,N;
bool cmp(Candy a,Candy b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
void add(int l,int r,int u,int v,int x)
{
	if(l==r)
	{
		++tree[v].num;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)
	{
		tree[v].rs=tree[u].rs;
		tree[v].ls=++sz;
		add(l,mid,tree[u].ls,tree[v].ls,x);
	}
	else
	{
		tree[v].ls=tree[u].ls;
		tree[v].rs=++sz;
		add(mid+1,r,tree[u].rs,tree[v].rs,x);	
	}
	tree[v].num=tree[tree[v].ls].num+tree[tree[v].rs].num;
}
int query(int l,int r,int u,int v,int x)
{
	if(l==r) return l;
	int mid=(l+r)/2;
	if(x<=tree[tree[v].ls].num-tree[tree[u].ls].num) return query(l,mid,tree[u].ls,tree[v].ls,x);
	else return query(mid+1,r,tree[u].rs,tree[v].rs,x-(tree[tree[v].ls].num-tree[tree[u].ls].num));
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j,x,y,k,p;
	for (i=1;i<=n;++i) scanf("%d",&a[i].x),b[i].x=a[i].x,b[i].y=i;
	sort(b+1,b+1+n,cmp);
	for (i=1;i<=n;++i) a[b[i].y].y=i,c[i]=a[b[i].y].x;
	for (i=1;i<=n;++i) root[i]=++sz,add(1,n,root[i-1],sz,a[i].y);
	while(m--)
	{
		scanf("%d%d%d",&x,&y,&k);
		printf("%d\n",c[query(1,n,root[x-1],root[y],k)]);
	}
}

·帶修主席樹

  • 上述的主席樹是一種優秀的處理曆史版本以及區間第k值得做法，但是現在我們遇到了一個棘手的問題，如果上述問題中，我們需要修改某一個值，并且同時線上詢問該怎麼做呢?
  • 我們發現，如果按照上述做法做，修改的時間将會是\(O(n\) \(log\) \(n)\),因為我們對于修改位置以後每一棵樹都要用log n 的時間去維護在這一位置上的值，顯然這樣的複雜度是不可接受的。
  • 我們可以想到使用樹狀數組去優化這種算法。
  • 我們發現樹狀數組的本質和主席樹的本質是一樣的，都是字首和，那我們能不能把它們兩個合并起來呢？
  • 答案是可以的，對于一顆樹狀數組上的每一個樹節點x，我們都建一顆線段樹，用來維護區間\([x-lowbit(x)+1..x]\)的所有資訊，這樣我們在修改的時候就遵循樹狀數組的修改原則修改。

例題

ZOJ2112 Dynamic Rankings

給定一個數列，包括兩個操作：

Q i j k 詢問區間[i..j]的第k小

C i t 将第i個數改成t

n<=50000,q<=10000

帶修主席樹裸題。

Code 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 50010
#define maxm 10010
#define maxN maxn+maxm
using namespace std;
struct Moon{
	int vol,ls,rs;
}tr[maxn];
int T,n,m,N,sz;
int a[maxn],dat[maxN],q1[maxn];
int root[maxn],kind[maxm],q2[maxn];
int qi[maxm],qj[maxm],qk[maxm],qt[maxm];
int lowbit(int x)
{
	return x&-x;
}
void clear()
{
	memset(tr,0,sizeof(tr));
	memset(root,0,sizeof(root));
}
int find(int x)
{
	int l,r,mid;
	for (l=1,r=N,mid=(l+r)/2;l<r;mid=(l+r)/2)
		if(dat[mid]<x) l=mid+1;else r=mid;
	return l;
}
void Modify(int &v,int l,int r,int x,int volue)
{
	if(!v) v=++sz;
	tr[v].vol+=volue;
	if(l==r) return;
	int mid=(l+r)/2;
	(x<=mid)?Modify(tr[v].ls,l,mid,x,volue):Modify(tr[v].rs,mid+1,r,x,volue);
}
void modify(int xx,int y,int c)
{
	for (;xx<=N;xx+=lowbit(xx)) Modify(root[xx],1,N,y,c);
}
int count()
{
	int sum=0;
	for (int i=1;i<=q1[0];++i) sum+=tr[tr[q1[i]].ls].vol;
	for (int i=1;i<=q2[0];++i) sum-=tr[tr[q2[i]].ls].vol;
	return sum;
}
int query(int ql,int qr,int k)
{
	memset(q1,0,sizeof(q1));
	memset(q2,0,sizeof(q2));
	int l=1,r=N,mid,Count,i;
	for (i=qr;i;i-=lowbit(i)) q1[++q1[0]]=root[i];
	for (i=ql-1;i;i-=lowbit(i)) q2[++q2[0]]=root[i];
	while(l<r)
	{
		Count=count(),mid=(l+r)/2;
		if(k<=Count)
		{
			for (i=1;i<=q1[0];++i) q1[i]=tr[q1[i]].ls;
			for (i=1;i<=q2[0];++i) q2[i]=tr[q2[i]].ls;
			r=mid;
		}
		else
		{
			for (i=1;i<=q1[0];++i) q1[i]=tr[q1[i]].rs;
			for (i=1;i<=q2[0];++i) q2[i]=tr[q2[i]].rs;
			l=mid+1,k-=Count;	
		}
	}
	return l;
}
int main()
{
	int i,j,k;char ch;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m),N=n;
		for (i=1;i<=n;++i) scanf("%d",&a[i]),dat[i]=a[i];
		for (i=1;i<=m;++i)
		{
			ch=getchar();while(ch!='Q'&&ch!='C') ch=getchar();
			if(ch=='Q') kind[i]=0,scanf("%d%d%d",&qi[i],&qj[i],&qk[i]);
			else kind[i]=1,scanf("%d%d",&qi[i],&qt[i]),dat[++N]=qt[i];
		} 
		sort(dat+1,dat+1+N),k=N,N=0;
		for (i=1;i<=k;++i) if(dat[i-1]!=dat[i]) dat[++N]=dat[i];
		for (i=1;i<=n;++i) modify(i,find(a[i]),1);
		for (i=1;i<=m;++i)
		{
			if(!kind[i]) printf("%d\n",dat[query(qi[i],qj[i],qk[i])]);
			else modify(qi[i],find(a[qt[i]]),-1),a[qi[i]]=qt[i],modify(qi[i],find(a[qi[i]]),1);	
		}clear();
	}
}

·Trie

可持久化trie和主席樹十分類似

差別：主席樹的主體是線段樹，而可持久化trie的主體是trie，主導思想都是字首和以及共用點。

如果你學完了主席樹，那麼可持久化trie也很容易了解了。 可持久化trie就是對于每個字元串S，我們都花\(O(|S|)\)的時間建立一棵有\(|S|\)個點的trie，将前面點的資訊複制到目前點，并且不斷建立點。

例題：【THUSC2015】異或問題

Description

給定長度為n的數列X={x1,x2,...,xn}和長度為m的數列Y={y1,y2,...,ym}，令矩陣A中第i行第j列的值Aij=xi xor yj，每次詢問給定矩形區域i∈[u,d],j∈[l,r]，找出第k大的Aij。

Input

第一行包含兩個正整數n,m，分别表示兩個數列的長度第二行包含n個非負整數xi；

第三行包含m個非負整數yj；

第四行包含一個正整數p，表示詢問次數；

随後p行，每行均包含5個正整數，用來描述一次詢問，每行包含五個正整數u,d,l,r,k，含義如題意所述。

Output

共p行，每行包含一個非負整數，表示此次詢問的答案。

Sample Input

3 3

1 2 4

7 6 5

3

1 2 1 2 2

1 2 1 3 4

2 3 2 3 4

Sample Output

6

5

1

Data Constraint

對于100%的資料，0<=Xi,Yj<2^31,

1<=u<=d<=n<=1000,

1<=l<=r<=m<=300000,

1<=k<=(d-u+1)*(r-l+1),

1<=p<=500

其中，部分測試資料有如下特征（互不包含）：

對于5%的資料，滿足1<=m<=1000, 1<=p<=10, k=1;

對于15%的資料，滿足1<=m<=3000, 1<=p<=200;

對于20%的資料，滿足p=1;

對于30%的資料，滿足k=1;

對于其餘30%的資料，沒有其他特征。

Code： 

#include<cstdio>
#include<iostream>
#define maxn 1010
#define maxm 300010
using namespace std;
struct Moon{
	int son[2],sz;
}point[40*maxm];
struct Candy{
	int x,y;
}b[maxn];
int n,m,q,u,d,l,r,k,Q,sz;
int x[maxn],y[maxm],Root[maxm],len[maxm]; 
void add(int u,int v,int x,int p)
{
	point[v].sz=point[u].sz+1;
	if(p<0) return;
	int y=(x>>p)&1;
	point[v].son[y]=++sz;
	point[v].son[!y]=point[u].son[!y];
	add(point[u].son[y],point[v].son[y],x,p-1);
}
int query(int k,int p)
{
	if(p<0) return 0;
	int sum=0,y;
	for (int i=u;i<=d;++i)
	{
		y=(x[i]>>p)&1;
		sum+=point[point[b[i].y].son[!y]].sz-point[point[b[i].x].son[!y]].sz;
	}
	if(sum>=k)
	{
		for (int i=u;i<=d;++i) 
		{
			y=(x[i]>>p)&1;
			b[i].y=point[b[i].y].son[!y];
			b[i].x=point[b[i].x].son[!y];
		}
		return query(k,p-1)+(1<<p);
	}else
	{
		for (int i=u;i<=d;++i) 
		{
			y=(x[i]>>p)&1;
			b[i].y=point[b[i].y].son[y];
			b[i].x=point[b[i].x].son[y];
		}
		return query(k-sum,p-1);	
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j,p;
	for (i=1;i<=n;++i) scanf("%d",&x[i]);
	for (i=1;i<=m;++i) 
	{
		scanf("%d",&y[i]);
		for (p=y[i];p;p/=2) ++len[i];
		Q=max(Q,len[i]);
	}Q--;
	for (i=1;i<=m;++i) Root[i]=++sz,add(Root[i-1],Root[i],y[i],Q);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d%d%d%d",&u,&d,&l,&r,&k);
		for (i=u;i<=d;++i) b[i].x=Root[l-1],b[i].y=Root[r];
		printf("%d\n",query(k,Q));
	}
}
上一篇: property和_property的一些小結
下一篇: 寒假英語學習，真正拒絕死記硬背，大幅度提高學習效率，請看一下方法作為一名重點學校教齡19年的英語教師，在給學生串講單詞前