主席树与整体二分浅析

发表于
字数统计: 1,787 | 阅读时长 ≈ 8

前言：

我觉得随便讲一下前言…对了我好菜弃坑弃坑

我们先来看一道题目，在分析题目时去深入理解主席树和整体二分算法

题目描述：

题目大意：

给你n个数，多次询问某段区间第k小的数。

输入格式：

第一行两个数n、m，n代表有多少个数，m代表询问数。

第二行n个数给出，不超过10^9。

接下来m行，每行三个数i,j,k，询问第i个数到第j个数中第k小的数是什么。

输出格式：

输出共m行，对每次询问的回答。

数据范围：

1<=n<=100000,1<=m<=5000。

主席树做法

主席树简析：

  • 其实这是一道赤裸裸的静态区间求第 K 大值的主席树模板
  • 主席树又叫做可持久化线段树，它支持查询历史版本，我们运用权值线段树来构造主席树
  • 若只使用一般的线段树，每个区间开一个线段树，那么空间复杂度极高，对于稍微大一点的数据便不可行了
  • 主席树恰恰避免了这一点(我觉得它要开的空间也很大…）我们假设每次询问一个区间，都要重新构造一棵线段树，很容易发现，前后两棵线段树，其实是有很多相似的信息的。
  • 经过冷静分析，发现相邻两棵线段树的形状，仅有一条链是不一样的，所以我们可以动态开点，如果对于一个和上一次对应位置相同的节点，我们直接赋相同的信息即可，若是新链的点，新建该节点，再信息更新递归往下，这样子整体的时间复杂度就是 O（nlogn)
  • 实际上主席树的形状并不是一棵严格意义的二叉树，它很像在一棵二叉树外面挂上一条一条新链

关于区间查找：

  • 从上面的分析我们可以发现，对于任意的 i ，我们都建了一棵树
  • 如果我们要查找 [1,i ] 中第 K 大的数，只需要判断左儿子所维护的信息是否大于我们要查找的 K ，大于则向左儿子递归，反之 K 减去这个信息的值再向右儿子递归
  • 由于我们构造的主席树具有可减性，我们要找区间 [ i , j ] 的 K 大数，只需要像查找线段树一样，求出 query（ j ) - query ( i - 1 ) 即可，类似于前缀和的思想
  • 我们来看一下AC代码

AC代码280ms：

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))

using namespace std;

const int N=200010;
int n,m,le,ri,k,cnt=0;
struct node{
    int l,r,val;
}T[N*60];
struct num{
    int val,id;
    inline bool operator <(const num &rhy) const{return val<rhy.val;}
}a[N];
int rank[N],root[N];

inline void insert(int &num,int &x,int l,int r){
    T[++cnt]=T[x];x=cnt;T[x].val++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(num<=mid) insert(num,T[x].l,l,mid);
    else insert(num,T[x].r,mid+1,r); 
}

inline int query(int t1,int t2,int l,int r,int k){
    if(l==r) return l;
    int temp=T[T[t2].l].val-T[T[t1].l].val;
    int mid=(l+r)>>1;
    if(k<=temp) return query(T[t1].l,T[t2].l,l,mid,k);
    else return query(T[t1].r,T[t2].r,mid+1,r,k-temp);
}

int main(){
    T[0].l=T[0].r=T[0].val=0;
    scanf("%d%d",&n,&m);root[0]=0;
    rep(i,1,n) scanf("%d",&a[i].val),a[i].id=i;
    sort(a+1,a+1+n);
    rep(i,1,n) rank[a[i].id]=i;
    rep(i,1,n) root[i]=root[i-1],insert(rank[i],root[i],1,n);
    while(m--){
        scanf("%d%d%d",&le,&ri,&k);
        printf("%d\n",a[query(root[le-1],root[ri],1,n,k)].val);
    }
    return 0;
}

PS：这只是静态主席树，主席树的入门题，还是很好理解的

整体二分做法

浅谈整体二分：

  • 整体二分是二分答案的进化版
  • 设想我们有 Q 个询问，每次询问一个答案，如果我们用一般的二分答案，那么理论上的时间复杂度就是 O ( f( n )* n ),其中 f（n）表示的是做一次询问的时间复杂度，对于 Q 的值很大时，就难以接受了
  • 所以我们不仅二分答案区间 l , r ,还二分询问区间 L ,R
  • 我们用 solve （l , r , L , R ) 表示操作 L ~ R 的数的权值和询问的答案区间为 l , r ,每次二分答案
  • 我们每次求出 mid 对询问的贡献，如果在区间内小于等于 mid 的个数（记为 cnt ）不超过 K ，那么最终的答案也不超过 K ，我们把这一类询问划分到左区间
  • 类似的如果 cnt 大于 K ，我们把它分到右区间，并且 cnt -= K
  • 换句话说，如果这个数贡献小于等于 mid ，我们就不用考虑了
  • 这样划分的层数是 logn ，算上 Q 次询问，再算上算贡献的复杂度，总的时间复杂度就是 O（QlognlogN) ，我们用树状数组维护…
  • 另外整体二分是需要离线操作的，在本题中跑的要比主席树慢…但是空间要比主席树小得多
  • 我们来看一下代码

AC代码730ms

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
#include<cstdio>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define INF 0x3f3f3f3f

using namespace std; 

const int N=500010;
int n,m,cnt=0,d,x,y,z;
struct question{
    int l,r,k,id,p;
}q[N];
int tree[N],ans[N];
question q1[N],q2[N];

inline int lowbit(int x){return x&-x;}

inline void add(int x,int k){while(x<=n) tree[x]+=k,x+=lowbit(x);}

inline int query(int x){int res=0;while(x>0) res+=tree[x],x-=lowbit(x);return res;}

inline void solve(int L,int R,int l,int r){
    if(l>r||L>R) return;
    if(l==r) {rep(i,L,R) if(q[i].p) ans[q[i].id]=l;return;}
    int mid=(l+r)>>1,left=0,right=0;
    rep(i,L,R){
        if(q[i].p){
            int temp=query(q[i].r)-query(q[i].l-1);
            if(temp>=q[i].k) q1[++left]=q[i];
            else q[i].k-=temp,q2[++right]=q[i];
        }
        else {
            if(q[i].l<=mid) q1[++left]=q[i],add(q[i].id,q[i].r);
            else q2[++right]=q[i];
        }
    }
    rep(i,1,left) if(!q1[i].p) add(q1[i].id,-q1[i].r);
    rep(i,1,left) q[L+i-1]=q1[i];
    rep(i,1,right) q[i+left+L-1]=q2[i];
    solve(L,L+left-1,l,mid);solve(L+left,R,mid+1,r);
}

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) {
        scanf("%d",&d);
        q[++cnt]=(question){d,1,0,i,0};
    }
    rep(i,1,m) {
        scanf("%d%d%d",&x,&y,&z);
        q[++cnt]=(question){x,y,z,i,1};
    }
    solve(1,cnt,-INF,INF);
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

后记

本人对整体二分的了解并不是很清晰（逃…
所以很口糊以后再补吧
另外我真菜…

联系qq： 953559040

微博： IncinblePan

洛谷： SherlockPan