|
?
对于主席树，先说说个人理解（待补），相当于空间换取时间，只有数据范围不是那么大的时候才能使用
一般开的空间为 N *4 + N *log N；具体实现的操作就是先copy一个原版本，之后再进行修改操作，再使用递归pushup上去，就完成了新版本的建立。
? 下面这道题，就是目前本人学到的主席树的第一个操作----查询定区间第k小的值，下面说说本人的理解。
1.为什么可以使用可持久化线段树？
试想一个问题，如果我们有方法 维护 落在 从小到大 【a，b】值域区间范围内的值的个数（初始化为0），那么我们不是就可以很轻易的利用单调性通过二分求解吗?
例如? ?2,3,4,5,6 这一段区间，明显可以找到第k小是几。
因此，通过使用可持久化线段树维护值域，我们从a[1]到a[n]扫描一遍，建立n个版本的线段树，不断更新落在每个值域的数cnt之后，利用一个非常重要的性质----- 试想 以 root【l - 1】表示记录扫描到
(1 到?l - 1)范围内的值域线段树版本1，以root【r】表示记录扫描到(1?到 r)范围内的值域线段树版本2， 那么对应查询区间【L,R】的cnt数量 =?对应查询区间【L,R】的版本 2 的数量 减去版本1的数量，这是因为，不妨如此思考，在l - 1的时候 a[l]到a[r]的数还没有被更新进入版本当中，但是当扫描到r的时候，这些数已经全部被更新到新版本（从左到右依次落在对应位置）当中了，因此这个时候它们的差值就产生在被更新的区间当中，由于值域具有单调性，并且第k小的数也是有一定单调性的，因此，我们便可以通过二分查找，缩小范围 找到确定的值域。（由于数据范围大，但是离散，需要用到离散化）
细节：
if(k <= cnt) return ask(tree[q].lc,tree[p].lc,l,mid,k);
return ask(tree[q].rc,tree[p].rc,mid + 1,r,k - cnt); //当前已经统计了cnt个数了。
在ask当中，我们不妨先以左节点对减去确定cnt值 ，如果偏大，那么一定落在左区间?，但当cnt值偏小往右区间查找的时候要注意，我们已经在左区间找到cnt个数了，因此要查找的数量为cnt - k。
例题：第K小数
#include<iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n, m;
struct SegmentTree
{
int lc,rc;
int cnt;
}tree[N * 4 + N * 17];
int tot,root[N];
int a[N];
vector<int> nums;
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build (int l, int r)
{
int p = ++tot;
if (l == r) return p;
int mid = (l + r) >> 1;
tree[p].lc = build(l, mid), tree[p].rc = build(mid+1, r);
return p;
}
int insert(int now,int l,int r,int x) //单点修改
{
int p = ++tot;
tree[p]= tree[now];
if(l == r)
{
tree[p].cnt++;
return p;
}
int mid =(l+r) >> 1;
if(x <= mid) tree[p].lc = insert(tree[now].lc,l,mid,x);
else
tree[p].rc = insert(tree[now].rc,mid + 1,r,x);
tree[p].cnt = tree[tree[p].lc].cnt + tree[tree[p].rc].cnt;
return p;
}
int ask(int q,int p,int l,int r,int k)
{
if(l == r) return r;
int cnt = tree[tree[q].lc].cnt - tree[tree[p].lc].cnt;
int mid = (l + r )>>1;
if(k <= cnt) return ask(tree[q].lc,tree[p].lc,l,mid,k);
return ask(tree[q].rc,tree[p].rc,mid + 1,r,k - cnt); //当前已经统计了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]));
for(int i = 1 ; i <= m ; i++)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", nums[ask(root[r], root[l-1], 0, nums.size()-1, k)]);
}
return 0;
}
?
|