主席树总结"/>
主席树总结
主席树总结
主席树一个可持久化数据结构。
什么叫可持久化数据结构???普通数据结构维护的是更新之后的状态,这个状态会覆盖之前的状态,使得之前的状态丢失,但可持久化数据结构并不是这样,通过建立多个不同版本的线段树,使得历史版本的线段树仍然可以查询到,更新并不会影响历史版本的状态,这种就叫可持久化线段树。
主席树其实可以维护的是历史版本的区间信息。
区间第K大
区间中小于某个值的个数
等等区间信息
可以说是非常方便的数据结构。同时可以与树上操作进行结合,进行解决某些树上问题,如树上第K小
POJ - 2104 K-th Number 区间第K小
模板题。。。查询root[l-1]到root[r]两个版本线段树之间的差异
用新版本的线段树去减去老版本的线段树,那么他们之间的信息就是他们的差值
所以查询第K小的信息就是
int query(int l,int r,int L,int R,int k){
if (l==r)return l;
int mid=MID(l,r);
int tmp=tree[tree[R].l].sum-tree[tree[L].l].sum;//区间中左儿子的个数
if (k<=tmp)query(l,mid,tree[L].l,tree[R].l,k);
else query(mid+1,r,tree[L].r,tree[R].r,k-tmp);
}
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define rep(i,j,k) for (int i=j;i<=k;i++) #define per(i,j,k) for (int i=j;i>=k;i--) #define pb push_back using namespace std; const int maxx = 100005; vector<int>v; struct node{int l,r,sum; }tree[maxx*40]; int a[maxx]; int root[maxx*40]; inline int L(int root){return root<<1;}; inline int R(int root){return root<<1|1;}; inline int MID(int l,int r){return (l+r)>>1;}; int cnt; void insert(int l,int r,int pre,int &now,int p){tree[++cnt]=tree[pre];now=cnt;tree[now].sum++;if (l==r){return ;}int mid=MID(l,r);if (p<=mid){insert(l,mid,tree[pre].l,tree[now].l,p);}else {insert(mid+1,r,tree[pre].r,tree[now].r,p);} } int query(int l,int r,int L,int R,int k){if (l==r)return l;int mid=MID(l,r);int tmp=tree[tree[R].l].sum-tree[tree[L].l].sum;if (k<=tmp)query(l,mid,tree[L].l,tree[R].l,k);else query(mid+1,r,tree[L].r,tree[R].r,k-tmp); } int main(){int n,m;while(~scanf("%d%d",&n,&m)){memset(tree,0,sizeof(tree));v.clear();rep(i,1,n){scanf("%d",&a[i]);v.pb(a[i]);}cnt=0;sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for (int i=1;i<=n;i++){a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;}rep(i,1,n){insert(1,n,root[i-1],root[i],a[i]);}while(m--){int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);}}return 0; }View Code
Count on a tree SPOJ – COT树上第K 小
主席树的入门题目,这道题的题意其实就是说,给你一棵树,询问在两个节点之间的路径上的区间第K小
我们如何把树上问题转换为区间问题呢?
其实DFS就可以,我们按照DFS的顺序,对线段树进行建树,那么这个树上问题就可以转换为区间问题了,
那么如何询问来表示两个节点之间的路径呢?
其实也很简单,我们建图的路径是从父亲节点到子节点。
那么其实很简单考虑一下图形
我们需要求树上第K小,但是我们知道,我们可以通过DFS序,把树上操作移植到序列操作,我们是从父亲节点到儿子节点建立的主席树。
那么我们两个不同版本的信息分别是
我们如何利用这两个版本的信息,得到答案呢???
我们来观察树链
我们发现这样一个有趣的东西,我们有ans=tree[L]+tree[R]-tree[LCA(L,R)]-tree[fa(LCA(L,R))]
也就是说我们需要的信息,是新的版本的线段树+原来版本的线段树-这两棵树的公共祖先的版本的线段树-公共祖先的父亲版本的线段树。
那么这个题就变得非常简单了,只是多了一个求LCA的操作
#include<iostream> #include<stdio.h> #include<string.h> #include<vector> #include<algorithm> #define LL long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define pb push_back using namespace std; const int maxx = 100005; struct node{int l,r,cnt; }tree[maxx*40]; inline int MID(int l,int r){return (l+r)>>1;}; int root[maxx*40]; int a[maxx]; int ver[maxx*2],Next[maxx*2],head[maxx]; int tot,cnt,n,m; int t=18; int fa[maxx],p[maxx][20],deepth[maxx]; vector<int>v; void add(int x,int y){ver[++tot]=y;Next[tot]=head[x];head[x]=tot;ver[++tot]=x;Next[tot]=head[y];head[y]=tot; } void update(int l,int r,int pre,int &now,int pos){now=++cnt;tree[now]=tree[pre];tree[now]t++;if (l==r)return;int mid=(l+r)>>1;if (pos<=mid)update(l,mid,tree[pre].l,tree[now].l,pos);elseupdate(mid+1,r,tree[pre].r,tree[now].r,pos); } int query(int l,int r,int L,int R,int k,int lca,int flac){if (l==r)return l;int tmp=tree[tree[R].l]t+tree[tree[L].l]t-tree[tree[lca].l]t-tree[tree[flac].l]t;int mid=MID(l,r);if (k<=tmp)return query(l,mid,tree[L].l,tree[R].l,k,tree[lca].l,tree[flac].l);elsereturn query(mid+1,r,tree[L].r,tree[R].r,k-tmp,tree[lca].r,tree[flac].r); } void dfs(int u,int pre){fa[u]=pre;deepth[u]=deepth[pre]+1;p[u][0]=pre;update(1,n,root[pre],root[u],a[u]);rep(i,1,18)p[u][i]=p[p[u][i-1]][i-1];for (int i=head[u];i;i=Next[i]){int y=ver[i];if (y==pre)continue;dfs(y,u);} } int LCA(int x,int y){if (deepth[x]>deepth[y])swap(x,y);per(i,t,0){if (deepth[p[y][i]]>=deepth[x])y=p[y][i];}if (x==y)return y;per(i,t,0){if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];}return p[x][0]; } int main(){while(~scanf("%d%d",&n,&m)){int uu,vv;memset(head,0,sizeof(head));rep(i,1,n){scanf("%d",&a[i]);v.pb(a[i]);}tot=1;cnt=0;sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());rep(i,1,n-1){scanf("%d%d",&uu,&vv);add(uu,vv);}rep(i,1,n){a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;}dfs(1,0);int k;while(m--){scanf("%d%d%d",&uu,&vv,&k);int lca=LCA(uu,vv);printf("%d\n",v[query(1,n,root[uu],root[vv],k,root[lca],root[fa[lca]])-1]);}}return 0; }View Code
HDU - 5919 F - Sequence II
题意
问这个区间里面有k个不同的数,把它们第一次出现的位置从小到大排序,问第k/2个位置是什么;,
….对于主席树,我们肯定是维护一个它第一次出现的位置,并维护区间和,从而利用区间第K小得到答案。
但是我们正着思考,这个似乎是没有前缀性质的,因为L区间版本的主席树,维护的是1-L区间的数字第一出现的次数,但是
转载于:.html
更多推荐
主席树总结
发布评论