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

可持久化线段树

news 来源：原创 2024/5/6 2:52:24

可持久化线段树相比可持久化Trie来说要简单一点，因为线段树的结构固定，无论如何添加信息结构都不会改变，时间复杂度为O(nlogn)

可持久化线段树维护的是值域，在数值上建立线段树，并维护每个数值区间一共有多少数

例题：第k小数255. 第K小数 - AcWing题库

给定长度为 N 的整数序列 A，下标为 1∼N。

现在要执行 M 次操作，其中第 i 次操作为给出三个整数 li , ri , ki，求 A[ li ],A[ li+1 ],…,A[ ri ] (即 A 的下标区间 [ li,ri ])中第 ki 小的数是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示整数序列 A。

接下来 M 行，每行包含三个整数 li ,ri ,ki ，用以描述第 i 次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第 k 小的数的数值。

每个结果占一行。

数据范围

N ≤ 105,M ≤ 104,|A[i]| ≤ 109

输入样例：

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

输出样例：

5
6
3

解题思路：

先来想如何求整体的第k小数，只需要递归即可，现在加入了区间限制，如果求的是1~R的第k小数，则只需要找刚好加完R个数的线段树版本，如果求的是1~L的第k小数，则只需要找刚好加完L个数的线段树版本,如果求的是L~R的第k小数，则可以用前缀和思想，用R的版本减去L的版本

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N=100010,M=10010;

int n,m;
int a[N];
vector<int> nums;

struct node
{
    int l,r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N],idx;

int find(int x)
{
    return lower_bound(nums.begin(),nums.end(),x) - nums.begin();
}

int build(int l,int r)
{
    int p = ++ idx;
    if(l == r)
    return p;
    int mid= l + r >> 1;
    tr[p].l=build(l,mid),tr[p].r=build(mid + 1,r);
    return p;
}

int insert(int p,int l,int r,int x)
{
    int q= ++ idx;
    tr[q]=tr[p];
    if(l == r)
    {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid)
    tr[q].l = insert(tr[p].l,l,mid,x);
    else
    tr[q].r = insert(tr[p].r,mid + 1,r,x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l == r)
    return r;
    int cnt=tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if(k<=cnt)
    return query(tr[q].l,tr[p].l,l,mid,k);
    else
    return query(tr[q].r,tr[p].r,mid + 1,r,k - cnt);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    
    root[0]=build(0,nums.size()-1);
    
    for(int i = 1; i <= n; i ++)
    {
        root[i] = insert(root[i - 1],0,nums.size() - 1,find(a[i]));
    }
    
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",nums[query(root[r],root[l - 1],0,nums.size() - 1,k)]);
    }
}