新内容

权值线段树和可持久化线段树

引入

下面要用到的权值线段树的概念类似于使用树状数组完成最长不下降子序列的那个题,

那么先复习一下怎么使用树状数组完成最长不上升子序列

要是连这个最基本的dp也看不懂的话,接下来要讲的不适于你理解

权值树状数组

以实现最长不上升子序列为例(B3637)

dp每一步转移的目标是,找到在自己前面的, 值小于等于自身的, 最长序列长度

在自己前面这个条件值自动满足的,因为dp转移的过程保证了是从前往后递推的

那么接下来要考虑的就是后面两个条件了

注意到树状数组可以维护前缀,所以我们把具体的数值对应下标,而下标的值是dp值

下标并不代表原始数组中的位置,而是对应值,填写在上面的才是要表达和维护的值

那么就可以求前缀最大值了,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const ll N=1e6+10;
ll tr[N],m=N-10;
ll lowerbit(ll x){return x&(-x);}
void update(ll x,ll k){
  for(;x<=m;x+=lowerbit(x)) tr[x]=max(tr[x],k);
}
ll query(ll x){
  ll maxn=0;
  for(;x>=1;x-=lowerbit(x)) maxn=max(maxn,tr[x])
  return maxn;
}
void solve(){
  ll n; cin>>n;
  ll maxn=0;
  for(int i=1;i<=n;i++){
    ll x; cin>>x;
    ll dp=query(x-1);
    update(x,dp+1);
    maxn=max(maxn,dp+1);
  }
  cout<<maxn<<endl;
}

权值线段树

权值线段树其实就是常规线段树加一个cnt计数的数组

通过这个,可以实现普通平衡树的所有功能

具体功能为:

1
2
3
4
5
6
1.add x
2.delete x
3.getrank x
4.get num by rank
5.get pre x
6.get suf x

逻辑和前面的树状数组类似,我们这里下标对应的也是值,而存储的值则是这个值出现的数量

此算法主要包含三个函数

修改

首先注意一下下标是和值对应的,所以何以通过计算mid得到需要修改的位置

1
2
3
4
5
6
7
8
9
10
void update(ll l,ll r,ll now,ll x,ll v){
  if(l==r){
    cnt[now]+=v;
    return;
  }
  ll mid=(l+r)>>1;
  if(x<=mid) update(l,mid,now<<1,x,v);
  if(x>mid) update(mid+1,r,now<<1|1,x,v);
  cnt[now]=cnt[now<<1]+cnt[now<<1|1];
}

查询排名

也是和上面一样的逻辑,只是多了一个计算排名的过程

这里我们把函数的返回值设定为,有多少个数字严格小于当前数字

1
2
3
4
5
6
ll getrank(ll l,ll r,ll now,ll x){
  if(l==r) return 0;
  ll mid=(l+r)>>1;
  if(x<=mid) return getrank(l,mid,now<<1,x);
  return getrank(mid+1,r,now<<1|1,x)+cnt[now<<1];
}

注意不要使用边界计算数字数量,而是使用计数数组

查询数字

这里其实就是看左边区间数字的个数,以及还要往右查询几个排名

要是不需要那么多,往左,否则往下递推,并减少所需排名数

1
2
3
4
5
6
ll getnum(ll l,ll r,ll now,ll x){
  if(l==r) return l;
  ll mid=(l+r)>>1;
  if(x<=cnt[now<<1]) return getnum(l,mid,now<<1,x);
  return getnum(mid+1,r,now<<1|1,x-cnt[now<<1]);
}

前后继

这个可以综合上面两个查询函数一起完成

1
2
if(op==5) cout<<tmp[getnum(1,n,1,getrank(1,n,1,x))-1]<<endl;
if(op==6) cout<<tmp[getnum(1,n,1,getrank(1,n,1,x+1)+1)-1]<<endl;

算出所需排名,然后再算出具体数字

然后为什么x+1能得到下一个数字呢?

因为我们会对原数组离散化,使得占用空间减少,所以何以加减1来得到

x+1有可能在当前版本不存在,但是能查询到这个数字相对于当前数组的排名,这样再返回去查数字,就能得到正确的数字了

可持久化线段树

这部分以单点修改查询的可持久化线段树为例讲解

什么是可持久化

可持久化的意思就是,能访问历史上的每一个版本的内容

每次修改都需要作为一个新的版本存在

怎么实现可持久化

显然线段树是个非常费空间的数据结构

那么,我们就不可能每次都单独重建一颗仅仅修改了一次的线段树了

实现思路:每次把修改时访问到的点新开出来,作为一个新的版本存在

怎么理解这个新的节点?

新的节点可以存在一条指向旧树节点的边,从而实现访问到没有修改的节点,

借用一下oiwiki的图:

这里只需要新增4个节点,以红色的1为根的就是新的版本

这样就能节省空间实现可持久化

可视化演示

光看图可能还是有点抽象,所以我写了一个可以单步播放的交互页面,把「动态开点 + 复用旧节点」的过程一步步画出来:

主席树可视化演示(构建过程 / 区间第 k 小)

页面里有两个视图:

  • 构建过程:逐版本单步播放,高亮的节点是本步新建的,虚线指针表示直接复用旧版本的节点;右侧同步显示离散化结果、节点数组(lc / rc / cnt)以及当前这一步到底改了什么。
  • 区间第 k 小:把版本 r 和版本 l-1 的树叠在一起,节点上的大字就是 cnt(r) - cnt(l-1),跟着演示看 k 是怎么决定往左还是往右走的。

支持键盘操作:← / → 单步,空格自动播放;也可以自己填 a[1..n] 重新建树,拿几组小数据手玩一遍,比看代码快得多。

代码实现

建树

其实这一步可以不要,当你知道了整棵树的值域范围时,第一次修改相当于在空树上创建一条链
可以直接通过update实现

但是这样显然是麻烦了,可以一次性构建成功

1
2
3
4
5
6
7
8
9
10
11
ll build(ll l,ll r){
  ll now=++cnt;
  if(l==r){
    tr[now]=a[l];
    return now;
  }
  ll mid=(l+r)>>1;
  ls[now]=build(l,mid);
  rs[now]=build(mid+1,r);
  return now;
}

这里使用了left_children和right_children的原因是,新的树你也不知道下一个节点在哪里,所以只能通过这种方式来手动连边,而不能通过mid来间接计算

其次就是需要动态开点,这里使用了cnt全局变量来计算当前点的编号

修改

其实就是,先获取旧的节点,继承全部信息,然后修改,最后连一下边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll update(ll l,ll r,ll prev,ll p,ll v){
  ll now=++cnt;
  ls[now]=ls[prev];
  rs[now]=rs[prev];
  tr[now]=tr[prev];
  if(l==r){
    tr[now]=v;
    return now;
  }
  ll mid=(l+r)>>1;
  if(p<=mid) ls[now]=update(l,mid,ls[prev],p,v);
  if(p>mid) rs[now]=update(mid+1,r,rs[prev],p,v);
  return now;
}

这段代码其实还可以简化一下,要是直接使用取地址符修改now参数,多一个参数,可以变成void类型,更加优雅

1
2
3
4
5
6
7
8
9
10
void update(ll l,ll r,ll&now,ll prev,ll p,ll v){
  now=++cnt;
  ls[now]=ls[prev];
  rs[now]=rs[prev];
  tr[now]=tr[prev];
  if(l==r) tr[now]=v;
  ll mid=(l+r)>>1;
  if(p<=mid) update(l,mid,ls[now],ls[prev],p,v);
  if(p>mid) update(mid+1,r,rs[now],rs[prev],p,v);
}

这么修改的逻辑是,now参数就是当前树上应该走在哪里,而prev就是旧版本应该走在哪里,同步更新即可

由于取地址了,后面函数中修改等价于上一层的同步修改

查询

查询的话其实就是正常的查询,但是注意查询时的根是根据你查询的版本号得到的那个根

1
2
3
4
5
6
ll query(ll l,ll r,ll now,ll p){
  if(l==r) return tr[now];
  ll mid=(l+r)>>1;
  if(p<=mid) return query(l,mid,ls[now],p);
  return query(mid+1,r,rs[now],p);
}

可持久化线段树的应用

除了前面提到的访问任意版本,还能查询区间第k小的数

实现方式是,逐个插入数字,按数组的顺组逐个update,然后同时遍历版本l-1和版本r,

没错,这里用的就是前缀和的思想

原理

相同 “ 位置 “ 节点的数量相减,就是这个区间内这一段多出来的点

然后和权值线段树根据排名查数字的逻辑一致,就能查询到这个数字了

查询函数的实现

对照上面的可视化页面第 ② 个视图看这段代码会更容易理解:cnt[ls[now2]] - cnt[ls[now1]] 就是画在节点上的那个大字,它决定了下一步往哪边走。

1
2
3
4
5
6
ll query(ll now1,ll now2,ll l,ll r,ll k){
  if(l==r) return l;
  ll mid=(l+r)>>1,lsz=cnt[ls[now2]]-cnt[ls[now1]];
  if(k<=lsz) return query(ls[now1],ls[now2],l,mid,k);
  return query(rs[now1],rs[now2],mid+1,r,k-lsz);
}

容易写错的点是返回值,这里我使用了离散化,所以返回l,实际写代码时请自己注意

完整代码示例

权值线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const ll N=1e5+10;
ll cnt[N*4],n;
void update(ll l,ll r,ll now,ll x,ll v){
  if(l==r){
    cnt[now]+=v;
    return;
  }
  ll mid=(l+r)>>1;
  if(x<=mid) update(l,mid,now<<1,x,v);
  if(x>mid) update(mid+1,r,now<<1|1,x,v);
  cnt[now]=cnt[now<<1]+cnt[now<<1|1];
}
ll getrank(ll l,ll r,ll now,ll x){
  if(l==r) return 0;
  ll mid=(l+r)>>1;
  if(x<=mid) return getrank(l,mid,now<<1,x);
  return getrank(mid+1,r,now<<1|1,x)+cnt[now<<1];
}
ll getnum(ll l,ll r,ll now,ll x){
  if(l==r) return l;
  ll mid=(l+r)>>1;
  if(x<=cnt[now<<1]) return getnum(l,mid,now<<1,x);
  return getnum(mid+1,r,now<<1|1,x-cnt[now<<1]);
}
void solve(){
  ll q; cin>>q;
  vector<pair<ll,ll>> a(q+1);
  vector<ll> tmp;
  for(int i=1;i<=q;i++){
    cin>>a[i].fs>>a[i].sd;
    if(a[i].fs==4) continue;
    tmp.pb(a[i].sd);
  }
  sort(tmp.begin(),tmp.end());
  tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
  n=tmp.size();
  for(int i=1;i<=q;i++){
    if(a[i].fs!=4)
      a[i].sd=lower_bound(tmp.begin(),tmp.end(),a[i].sd)-tmp.begin()+1;
    ll op=a[i].fs,x=a[i].sd;
    if(op==1) update(1,n,1,x,1);
    if(op==2) update(1,n,1,x,-1);
    if(op==3) cout<<getrank(1,n,1,x)+1<<endl;
    if(op==4) cout<<tmp[getnum(1,n,1,x)-1]<<endl;
    if(op==5) cout<<tmp[getnum(1,n,1,getrank(1,n,1,x))-1]<<endl;
    if(op==6) cout<<tmp[getnum(1,n,1,getrank(1,n,1,x+1)+1)-1]<<endl;
  }
}
/*
1.add x
2.delete x
3.getrank x
4.get num by rank
5.get pre x
6.get suf x
*/
signed main(){
  fast
  solve();
  return 0;
}

主席树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const ll N=2e5+10;
const ll MAXN=20*N;
ll cnt[MAXN],a[N],id=0
ll ls[MAXN],rs[MAXN],root[N];
ll update(ll l,ll r,ll prev,ll p){
  ll now=++id;
  ls[now]=ls[prev];
  rs[now]=rs[prev];
  cnt[now]=cnt[prev]+1;
  if(l==r) return now;
  ll mid=(l+r)>>1;
  if(p<=mid) ls[now]=update(l,mid,ls[prev],p);
  if(p>mid) rs[now]=update(mid+1,r,rs[prev],p);
  return now;
}
ll query(ll now1,ll now2,ll l,ll r,ll k){
  if(l==r) return l;// fix
  ll mid=(l+r)>>1,lsz=cnt[ls[now2]]-cnt[ls[now1]];// fix
  if(k<=lsz) return query(ls[now1],ls[now2],l,mid,k);
  return query(rs[now1],rs[now2],mid+1,r,k-lsz);
}
void solve(){
  ll n,m; cin>>n>>m;
  vector<ll> tmp;
  for(int i=1;i<=n;i++) cin>>a[i],tmp.pb(a[i]);
  sort(tmp.begin(),tmp.end());
  tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
  ll t=tmp.size();
  for(int i=1;i<=n;i++){
    a[i]=lower_bound(tmp.begin(),tmp.end(),a[i])-tmp.begin()+1;
    root[i]=update(1,t,root[i-1],a[i]);// fix
  }
  while(m--){
    ll l,r,k; cin>>l>>r>>k;
    cout<<tmp[query(root[l-1],root[r],1,t,k)-1]<<endl;// fix l-1
  }
}
signed main(){
  fast
  solve();
  return 0;
}

代码中注释fix的地方是我曾经写错的地方,希望对你们有帮助