当前位置：首页 > news >正文

模板主席树查询区间k小

news 来源：原创 2024/5/19 21:50:42

模板：

有一个长 $n$ 的序列， $m$ 个询问，每次查询区间 $[l, r]$ 的第 $k$ 小是多少

Solution:

可持久化线段树查询静态区间 $k$ 小，利用可持久化线段树的多重线段树，以 $O (n + n l o g n)$ 的空间存储 $n$ 棵线段树的特点，来保存一颗前缀权值线段树，随后在 $[l, r]$ 的权值线段树上二分

思想：

不妨考虑一个简单问题，我们只查询序列的总体 $k$ 小，并且限制使用权值线段树来解决问题，显然我们只需要在线段树上二分即可。那要查询 $[l, r]$ 的区间 $k$ 小，我们可以想办法构造出一颗 $[l, r]$ 的权值线段树，直接在上面二分即可解决问题。

主席树就是利用这样的思想， $[l, r]$ 的权值线段树等价于 $[1, r]$ 的权值线段树减去 $[1, l - 1]$ 的权值线段树，但是多棵线段树难以保存，并且维护每一棵线段树耗费时间巨大，每一棵都是 $n l o g n$ ，总复杂度至少就是 $O(n^{2}logn)$ ，这是不理想的。可持久化线段树恰恰能保存多颗线段树于一身，并且添加一颗新的线段树时空复杂度都是 $O (l o g n)$ ，所以可以保存所有的前缀权值线段树在一颗可持久化线段树上，这样只需要在 $[1, l - 1]$ 和 $[1, r]$ 的差值权值线段树上二分即可。

而每次构建新的权值线段树，就是在 $v ers i o n [i - 1]$ 的基础上在 $a [i]$ 的位置上+1即可

二分：

在差值权值线段树上二分，如果左边的总数 $\geq k$ ，那么直接在左边查询即可，否则查询右边的 $k - t o t$ 小， $t o t$ 是左边子树的元素个数和

洛谷 $P 3834$

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

int version[1000005],tree[30000005],lson[30000005],rson[30000005];
int n,m,cnt,vp,a[1000005],b[1000005];
inline int& rs(int x){return rson[x];}
inline int& ls(int x){return lson[x];}

void build(int l,int r,int x)
{
    if(l==r) return;
    int mid=l+r>>1;
    if(!ls(x)) ls(x)=++cnt;
    if(!rs(x)) rs(x)=++cnt;
    build(l,mid,ls(x));
    build(mid+1,r,rs(x));
}

inline void push_up(int x){tree[x]=tree[ls(x)]+tree[rs(x)];}

void modify(int nl,int l,int r,int x,int nx)
{
    if(l==r){tree[nx]=tree[x]+1;return;}
    int mid=l+r>>1;
    if(nl<=mid) ls(nx)=++cnt,rs(nx)=rs(x),modify(nl,l,mid,ls(x),ls(nx));
    else ls(nx)=ls(x),rs(nx)=++cnt,modify(nl,mid+1,r,rs(x),rs(nx));
    push_up(nx);
}

void insert(int k)
{
    version[++vp]=++cnt;
    modify(k,1,n,version[vp-1],version[vp]);
}

int query(int l,int r,int lx,int rx,int k)
{
    if(l==r) return b[l];
    int mid=l+r>>1,tot=tree[ls(rx)]-tree[ls(lx)];
    if(k<=tot) return query(l,mid,ls(lx),ls(rx),k);
    return query(mid+1,r,rs(lx),rs(rx),k-tot);
}

inline int query(int l,int r,int k)
{
    return query(1,n,version[l-1],version[r],k);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m; 
    build(1,n,version[0]=++cnt);//不要写成build(1,n,1)，可以写成build(1,n,0)
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
        insert(a[i]);
    }
    while(m--)
    {
        int l,r,k; cin>>l>>r>>k;
        printf("%d\n",query(l,r,k));
    }
    return 0;
}