可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
所以这里讲的可持久化线段树也叫函数式线段树(又叫主席树……因为先驱就是fotile主席Orz……)。
先了解一下主席树
很详细的介绍了函数式线段树(主席树)。
主席树其实就是很多棵线段树，由于每次更新只需要更新logN个节点，所以主席树的内存不用到达N*N的级别，只需要NlogN级别。。
每次更新的时候都新建一个节点，然后递归下去，更新了logN个节点，其他的节点就与之前建的线段树一起共用。。
hdu4417 Super Mario
题意：给定一段区间每个点有个高度。在m次询问中每次给出左右端点和可以到达的高度，统计有多少个是小于到达高度
做法：主席树 + 离散化。。输入比较大，所以需要离散化。。tot统计总的节点个数，结构体的sum是统计出现的数的个数，每次询问[l, r] x的时候，就在第r棵线段树-第l-1棵线段树( 相当于[l, r]区间的数 ) 里面找小于等于x的个数。。建议先看代码，看不懂再去在主席树的介绍，这样重复的看。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 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 }
spoj 3267 D-query
对于每一个起始位置，都建立一棵主席树, 从前往后更新，更新在当前位置，如果这个数先前出现过，就减去先前出现的位置(由于主席树共用了一部分的节点，所以减去先前出现的位置就要新建一棵树)。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std;11 12 #define mnx 3005013 #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 int a[mnx], b[mnx];22 int root[mnx], tot, vis[mnx*40];23 struct node{24 int ls, rs, sum;25 }p[mnx*25];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 L, int R, int l, int r ){46 if( L <= l && R >= r ){47 return p[i].sum;48 }49 int ret = 0, m = ( l + r ) >> 1;50 if( L <= m ) ret += query( p[i].ls, L, R, l, m );51 if( R > m ) ret += query( p[i].rs, L, R, m + 1, r );52 return ret;53 }54 int main(){55 int n, m;56 while( scanf( "%d", &n ) != EOF ){57 tot = 0;58 memset( vis, 0, sizeof(vis) );59 for( int i = 1; i <= n; i++ ){60 scanf( "%d", &a[i] );61 }62 root[0] = build( 1, n );63 for( int i = 1; i <= n; i++ ){64 int t = update( i, 1, root[i-1], 1, n ); 65 if( vis[a[i]] ){66 root[i] = update( vis[a[i]], -1, t, 1, n );67 }68 else root[i] = t;69 vis[a[i]] = i;70 }71 int l, r;72 scanf( "%d", &m );73 while( m-- ){74 scanf( "%d %d", &l, &r );75 int ans = query( root[r], l, r, 1, n );76 printf( "%d\n", ans );77 }78 }79 return 0;80 }
hdu4348 To the moon
具体看这里
开始的时候写挫了，区间询问。。。主要还是对主席树不够理解。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std; 11 12 #define mnx 100050 13 #define ll long long 14 #define mod 1000000007 15 #define inf 223372036854775807 16 #define eps 1e-10 17 #define Pi acos(-1.0); 18 #define lson l, m, rt << 1 19 #define rson m+1, r, rt << 1 | 1 20 21 int tot, root[mnx]; 22 struct node{ 23 int ls, rs; 24 ll sum, lz; 25 }p[mnx*25]; 26 int build( int l, int r ){ 27 int rt = tot++; 28 p[rt].lz = 0; 29 if( l == r ){ 30 scanf( "%I64d", &p[rt].sum ); 31 return rt; 32 } 33 int m = ( l + r ) >> 1; 34 p[rt].ls = build( l, m ); 35 p[rt].rs = build( m + 1, r ); 36 p[rt].sum = p[p[rt].ls].sum + p[p[rt].rs].sum; 37 return rt; 38 } 39 int update( int L, int R, int d, int l, int r, int pre ){ 40 int rt = tot++; 41 p[rt] = p[pre]; 42 p[rt].sum += (ll)d * ( R - L + 1 ); 43 if( L == l && R == r ){ 44 p[rt].lz += (ll)d; 45 return rt; 46 } 47 int m = ( l + r ) >> 1; 48 if( R <= m ) p[rt].ls = update( L, R, d, l, m, p[pre].ls ); 49 else if( L > m ) p[rt].rs = update( L, R, d, m + 1, r, p[pre].rs ); 50 else{ 51 p[rt].ls = update( L, m, d, l, m, p[pre].ls ); 52 p[rt].rs = update( m + 1, R, d, m + 1, r, p[pre].rs ); 53 } 54 //p[rt].lz = p[p[rt].ls].lz + p[p[rt].rs].lz; 55 return rt; 56 } 57 ll query( int L, int R, int l, int r, int i ){ 58 ll ret = 0; 59 if( L == l && R == r ){ 60 return p[i].sum; 61 } 62 int m = ( l + r ) >> 1; 63 if( R <= m ) ret += query( L, R, l, m, p[i].ls ); 64 else if( L > m ) ret += query( L, R, m + 1, r, p[i].rs ); 65 else{ 66 ret += query( L, m, l, m, p[i].ls ); 67 ret += query( m + 1, R, m + 1, r, p[i].rs ); 68 } 69 return ret + p[i].lz * ( R - L + 1 ); 70 } 71 int main(){ 72 int n, m, cur, cnt; 73 while( scanf( "%d %d", &n, &m ) != EOF ){ 74 tot = 0, cnt = 0; 75 root[0] = build( 1, n ); cur = root[0]; 76 char ch[3]; 77 int l, r, t, d; 78 while( m-- ){ 79 scanf( "%s", ch ); 80 if( ch[0] == 'C' ){ 81 scanf( "%d %d %d", &l, &r, &d ); 82 root[++cnt] = update( l, r, d, 1, n, cur ); 83 cur = root[cnt]; 84 } 85 else if( ch[0] == 'Q' ){ 86 scanf( "%d %d", &l, &r ); 87 ll ans = query( l, r, 1, n, cur ); 88 printf( "%I64d\n", ans ); 89 } 90 else if( ch[0] == 'H' ){ 91 scanf( "%d %d %d", &l, &r, &t ); 92 ll ans = query( l, r, 1, n, root[t] ); 93 printf( "%I64d\n", ans ); 94 } 95 else{ 96 scanf( "%d", &t ); 97 cnt = t; 98 cur = root[t]; 99 }100 }101 }102 return 0;103 }
题目：
No Game No Life
3000ms / 102400KB / C, C++ or JAVA
Description
Cirno likes RPG game very much but not good at it.One day she get a new RPG game. When the battle begin, there will be n monsters stand in a row from 1 to n. And the HP of them are hp1, hp2, ... , hpn. Cirno has so many skills, a skill can attack the monsters from L to R with x damage. In the battle Cirno will attack the monsters use her skills, and sometime she wants to know the current hp of the monster at position x.
Because Cirno is not good at RPG game, she will use SL(save and load) fundamental to play this game. It is to say that Cirno may save a new archive or load a old archive at sometime.
A monster won’t change his position even he is dead( hp down to 0 ).
Input Description
The first line of the input contains an integer T(1 <= T <= 20) which means the number of test cases. For each case, the first line contains two integers n, m (1 <= n, m <= 50000). The next line contains n space-separated integers hp[1], hp[2], ... hp[n]. (0 < hp[i] <= 1000000). Then m lines follow, each line will satisfy one of the following format: 1 L R x : means attack each monster from L to R, and the damage is x.(1 <= x <= 20000) 2 : means save a new archive. If there were k archives, this would be the (k+1)th. 3 x: means load the x-th archive. It is guaranteed that the x-th archive is exist. 4 x: means query the x-th monsert’s hp.
Output Description
For each case X, output “Case #X:" first, in a single line. Then for each query (4 x), output the hp of the x-th monsert. If the x-th monsert has been dead, output 0.
Sample Input
15 1410 10 10 10 104 31 3 5 224 31 1 5 324 53 14 31 2 5 1004 223 24 3
Sample Output
Case #1:1085805
主席树， 和上一道差不多。。区间更新+单点询问，其实单点询问可以直接套区间询问。。这里用了不同update和query的方法，感觉更好理解。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 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 int tot, root[mnx], save[mnx], hp[mnx];22 struct node{23 int ls, rs, sum;24 }p[mnx*25];25 int build( int l, int r ){26 int rt = tot++;27 p[rt].sum = 0;28 if( l == r ){29 return rt;30 }31 int m = ( l + r ) >> 1;32 p[rt].ls = build( l, m );33 p[rt].rs = build( m + 1, r );34 return rt;35 }36 int update( int L, int R, int d, int l, int r, int pre ){37 int rt = tot++;38 p[rt] = p[pre];39 if( L == l && R == r ){40 p[rt].sum += d;41 return rt;42 }43 int m = ( l + r ) >> 1;44 if( R <= m ) p[rt].ls = update( L, R, d, l, m, p[pre].ls );45 else if( L > m ) p[rt].rs = update( L, R, d, m + 1, r, p[pre].rs );46 else{47 p[rt].ls = update( L, m, d, l, m, p[pre].ls );48 p[rt].rs = update( m + 1, R, d, m + 1, r, p[pre].rs );49 }50 return rt;51 }52 int query( int x, int l, int r, int i ){53 if( l == r ){54 return p[i].sum;55 }56 int ret = 0, m = ( l + r ) >> 1;57 if( x <= m ) ret += query( x, l, m, p[i].ls );58 else ret += query( x, m + 1, r, p[i].rs );59 return ret + p[i].sum;60 }61 int main(){62 int n, m, cur, cnt, cas, cont = 1;63 scanf( "%d", &cas );64 while( cas-- ){65 scanf( "%d %d", &n, &m );66 for( int i = 1; i <= n; i++ ){67 scanf( "%d", &hp[i] );68 }69 tot = 0, cnt = 0;70 root[0] = build( 1, n ); cur = root[0];71 int ch;72 int l, r, t, d, i = 0;73 printf( "Case #%d:\n", cont++ );74 while( m-- ){75 scanf( "%d", &ch );76 if( ch == 1 ){77 scanf( "%d %d %d", &l, &r, &d );78 root[++cnt] = update( l, r, d, 1, n, cur ); 79 cur = root[cnt];80 }81 else if( ch == 2){82 save[++i] = cur;83 }84 else if( ch == 4 ){85 scanf( "%d", &l );86 printf( "%d\n", max( hp[l] - query( l, 1, n, cur ), 0 ) );87 }88 else{89 scanf( "%d", &t );90 cur = save[t];91 }92 }93 }94 return 0;95 }