首页 > 代码库 > 主席树 | | 可持久化线段树
主席树 | | 可持久化线段树
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
所以这里讲的可持久化线段树也叫函数式线段树(又叫主席树……因为先驱就是fotile主席Orz……)。
先了解一下主席树
http://seter.is-programmer.com/posts/31907.html 很详细的介绍了函数式线段树(主席树)。
主席树其实就是很多棵线段树，由于每次更新只需要更新logN个节点，所以主席树的内存不用到达N*N的级别，只需要NlogN级别。。
每次更新的时候都新建一个节点，然后递归下去，更新了logN个节点，其他的节点就与之前建的线段树一起共用。。
http://acm.hdu.edu.cn/showproblem.php?pid=4417 hdu4417 Super Mario
题意：给定一段区间每个点有个高度。在m次询问中每次给出左右端点和可以到达的高度，统计有多少个是小于到达高度
做法：主席树 + 离散化。。输入比较大，所以需要离散化。。tot统计总的节点个数，结构体的sum是统计出现的数的个数，每次询问[l, r] x的时候，就在第r棵线段树-第l-1棵线段树( 相当于[l, r]区间的数 ) 里面找小于等于x的个数。。建议先看代码，看不懂再去在主席树的介绍，这样重复的看。。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<string> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 #include<vector> 9 10 using namespace std;11 12 #define mnx 10005013 #define ll long long14 #define mod 100000000715 #define inf 22337203685477580716 #define eps 1e-1017 #define Pi acos(-1.0);18 #define lson l, m, rt << 119 #define rson m+1, r, rt << 1 | 120 21 ll a[mnx], b[mnx];22 int root[mnx], tot;23 struct node{24 int ls, rs, sum;25 }p[mnx*20];26 int build( int l, int r ){27 int rt = tot++;28 p[rt].sum = 0;29 if( l == r ) return rt;30 int m = ( l + r ) >> 1;31 p[rt].ls = build( l, m );32 p[rt].rs = build( m + 1, r );33 return rt;34 }35 int update( int x, int v, int i, int l, int r ){36 int rt = tot++;37 p[rt] = p[i];38 p[rt].sum += v;39 if( l == r ) return rt;40 int m = ( l + r ) >> 1;41 if( x <= m ) p[rt].ls = update( x, v, p[i].ls, l, m );42 else p[rt].rs = update( x, v, p[i].rs, m + 1, r );43 return rt;44 }45 int query( int i, int j, int k, int l, int r ){46 if( l == r ) return p[i].sum - p[j].sum;47 int ret = 0, m = ( l + r ) >> 1;48 if( k > m ){49 ret += ( p[p[i].ls].sum - p[p[j].ls].sum );50 ret += query( p[i].rs, p[j].rs, k, m + 1, r );51 }52 else{53 ret += query( p[i].ls, p[j].ls, k, l, m );54 }55 return ret;56 }57 int main(){58 int cas, cnt = 1;59 scanf( "%d", &cas );60 while( cas-- ){61 tot = 0;62 int n, m;63 scanf( "%d %d", &n, &m );64 for( int i = 1; i <= n; i++ ){65 scanf( "%I64d", &a[i] );66 b[i] = a[i];67 }68 sort( b + 1, b + 1 + n );69 int tmp = unique( b + 1, b + 1 + n ) - b - 1;70 tmp++, b[tmp] = inf;71 root[0] = build( 1, tmp );72 for( int i = 1; i <= n; i++ ){73 int k = lower_bound( b + 1, b + 1 + tmp, a[i] ) - b;74 root[i] = update( k, 1, root[i-1], 1, tmp ); 75 }76 printf( "Case %d:\n", cnt++ );77 while( m-- ){78 int l, r; ll v;79 scanf( "%d %d %I64d", &l, &r, &v );80 l++, r++;81 int k = upper_bound( b + 1, b + 1 + tmp, v ) - b - 1;82 int ans = 0;83 if( k > 0 ) ans = query( root[r], root[l-1], k, 1, tmp );84 printf( "%d\n", ans );85 }86 }87 return 0;88 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。