[福利]可持久化线段树
Background
为什么说本题是福利呢?因为这是一道非常直白的可持久化线段树的练习题,目的并不是虐人,而是指导你入门可持久化数据结构。
Description
线段树有个非常经典的应用是处理RMQ问题,即区间最大/最小值询问问题。现在我们把这个问题可持久化一下:
Q k l r 查询数列在第k个版本时,区间[l, r]上的最大值
M k p v 把数列在第k个版本时的第p个数修改为v,并产生一个新的数列版本
最开始会给你一个数列,作为第1个版本。每次M操作会导致产生一个新的版本。
修改操作可能会很多呢,如果每次都记录一个新的数列,空间和时间上都是令人无法承受的。
所以我们需要可持久化数据结构。
对于最开始的版本1,我们直接建立一颗线段树,维护区间最大值。
修改操作呢?我们发现,修改只会涉及从线段树树根到目标点上一条树链上logn个节点而已,其余的节点并不会受到影响。所以对于每次修改操作,我们可以只重建修改涉及的节点即可。
需要查询第k个版本的最大值,那就从第k个版本的树根开始,像查询普通的线段树一样查询即可。
要计算好所需空间哦。
Format
Input
第一行两个整数N, Q。N是数列的长度,Q表示询问数
第二行N个整数,是这个数列
之后Q行,每行以0或者1开头,0表示查询操作Q,1表示修改操作M,格式为
0 k l r 查询数列在第k个版本时,区间[l, r]上的最大值 或者
1 k p v 把数列在第k个版本时的第p个数修改为v,并产生一个新的数列版本
Output
对于每个M询问,输出正确答案
Sample 1
Input
4 5
1 2 3 4
0 1 1 4
1 1 3 5
0 2 1 3
0 2 4 4
0 1 2 4
Output
4
5
4
4
Limitation
1s, 262144KiB for each test case.
Hint
N <= 10000
Q <= 100000
对于每次询问操作的版本号k保证合法,区间[l, r]一定满足1 <= l <= r <= N
最后
他还有一个高贵冷艳的名字:主席树。 然后你A了就可以去装13了
什么是主席树
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
因此可持久化线段树也叫函数式线段树又叫主席树。
C++ Code
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;
const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
int n,m,st_size,st_cnt;
int a[10000+1];
int st_t[1000000+1];
int st_l[1000000+1];
int st_r[1000000+1];
int st_mid[1000000+1];
int st_lc[1000000+1];
int st_rc[1000000+1];
int st_max[1000000+1];
void push_up_1(int now)
{
st_max[now]=max(st_max[st_lc[now]],st_max[st_rc[now]]);
}
void build_st_1(int &now,int l,int r)
{
if (now==0)
now=++st_size;
st_l[now]=l;
st_r[now]=r;
st_mid[now]=(l+r)/2;
if (l==r)
st_max[now]=a[l];
else if (l<r)
{
if (l<=st_mid[now])
build_st_1(st_lc[now],l,st_mid[now]);
if (st_mid[now]+1<=r)
build_st_1(st_rc[now],st_mid[now]+1,r);
push_up_1(now);
}
}
void copy_1(int now,int last)
{
st_l[now]=st_l[last];
st_r[now]=st_r[last];
st_mid[now]=st_mid[last];
st_lc[now]=st_lc[last];
st_rc[now]=st_rc[last];
st_max[now]=st_max[last];
}
void update_st_1(int &now,int last,int p,int d)
{
now=++st_size;
copy_1(now,last);
if (st_l[now]==p&&p==st_r[now])
st_max[now]=d;
else
{
if (p<=st_mid[now])
update_st_1(st_lc[now],st_lc[last],p,d);
else if (st_mid[now]+1<=p)
update_st_1(st_rc[now],st_rc[last],p,d);
push_up_1(now);
}
}
int sum_st_max_1(int now,int l,int r)
{
if (now==0)
return oo_min;
else if (st_l[now]==l&&r==st_r[now])
return st_max[now];
else if (r<=st_mid[now])
return sum_st_max_1(st_lc[now],l,r);
else if (st_mid[now]+1<=l)
return sum_st_max_1(st_rc[now],l,r);
else
return max(sum_st_max_1(st_lc[now],l,st_mid[now]),sum_st_max_1(st_rc[now],st_mid[now]+1,r));
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
st_size=st_cnt=0;
memset(st_t,0,sizeof(st_t));
memset(st_l,0,sizeof(st_l));
memset(st_r,0,sizeof(st_r));
memset(st_mid,0,sizeof(st_mid));
memset(st_lc,0,sizeof(st_lc));
memset(st_rc,0,sizeof(st_rc));
memset(st_max,0,sizeof(st_max));
build_st_1(st_t[++st_cnt],1,n);
for (int i=1;i<=m;i++)
{
int o,v,l,r,d;
scanf("%d%d",&o,&v);
if (o==0)
{
scanf("%d%d",&l,&r);
printf("%d\n",sum_st_max_1(st_t[v],l,r));
}
else if (o==1)
{
scanf("%d%d",&l,&d);
update_st_1(st_t[++st_cnt],st_t[v],l,d);
}
}
}
}
Source
Vijos Original