线段树三(可持久化线段树&主席树)

本文代码是我临时手打的,没有测试,并不保证细节上的正确性

首先线段树是一个性质非常好的一棵树,因此在线段树的神仙的操作就会有很多
首先对于一颗线段树如果我们需要操作去查找历史版本的话,那样就需要可持久化了,
首先需要历史版本的信息,也就是说我们会在各种意义上存下来每个版本的值
先不管可持久化这个东西

我们来分析一下权值线段树,权值线段树支持查询区间$[1, n]$的$rank$, 和$rank$值是多少的某个元素是什么
对于权值线段树的知识相信网上很多博客都有讲,我也就大致口胡一下具体实现吧
首先对于所有数进行离散化,然后根据离散化的值为$pos$,我们对线段树的$pos$的位置实现单点$+1$
这样我要查询第$k$大的时候我就可以通过想平衡树那样往左走或者往右走来实现了
至于查询某个元素的排名直接在离散化数组还有线段树里随便整一下就出来了

至于我们为什么来说这么就的权值线段树呢?
因为我们如果依次按照原数组的顺序去修改权值线段树在 离散化数组的排名 处的值
那样我们是不是可以得到$n$颗线段树, 而且若要仔细想想就能发现 这$n$颗线段树符合前缀和的性质
因此我们若是要求一下区间$[l, r]$的第$k$大之类的我们就可以用第$r$颗权值线段树 - 第$l-1$颗线段树然后对得到的这颗线段树进行一下普通的权值线段树做的事情就行
但是一般来说开$n$颗线段树显然不是我们能接受的代价,显然就要说到我们这次的主角rope,它可以支持...呸跑题了
显然这就要说到我们这次的主角可持久化线段树/函数式线段树/主席树了
首先我们对于第i颗权值线段树和第i+1颗线段树我们可以很容易的发现他们大致可能会长这个样子
不同的权值线段树的区别
通过上图我们就很容易发现他们之间的区别仅仅是只有三个结点不同,所以我们就通常不管是怎么样
对于其中一种方法就是首先我们先复制一下这颗权值线段树然后逐渐改变这三个结点,
但这样显然对于空间需求是巨大的,先不考虑复制所产生的时间代价
所以说显然这种代价一般来说是接受不了的,所以我们就会想到一点就是访问一棵树的时候,只要知道根节点就可以访问到任何结点,同意对于任何结点要想遍历他的子树必须能知道他的子结点,对于其他结点我们必须能知道他的父亲结点,但显然这道题中完全不需要维护父亲结点,因此我们可以知道一个很简单的性质,只要我们要是新建一个根结点,并且指向原来两个根结点的孩子,我们就可以绕过根节点,同样这个结点,只需要我们后面在新建一个结点,然后到时候更改一下父亲结点对应的指针就好,很容易得到这张图,当然对应的权值肯定要修改的
主席树
因此首先我们无法像普通的线段树那样去分配空间,因此我们就要像字典树或者平衡树那样分配空间,并且这样不能像普通的平衡树开一个$root$变量来存储根结点,因为根结点会有很多,因此我们还需要在开一个$root[maxn]$来存储

const int maxn = 2e5;
struct node
{
    int l, r, val;
}tr[maxn * 40 + 5]; // 一般都是*40 其实可以算,不过一般不会卡空间,所以多开点也无所谓
int root[maxn + 5], cnt;
int build(int l, int r) // 这里要么有返回值要么是没有返回值,但要引用调用一个变量 void build(int& pos, int l, int r) 这样写也一样
{
    int now = ++ cnt; // 内存池常用用法
    if(l != r)
    {
        int mid = (l + r) >> 1;
        tr[now].l = build(l, mid); // 需要找到他的左儿子的结点
        tr[now].r = build(mid + 1, r); // 需要找到他的右儿子的结点
    }
    if(l == r)
    {
        // 可以存储一些信息,不过对于权值线段树第0个版本里面所有的值为0
    }
    return now; // 需要把这个返回
}
int update(int pos, int l, int r, int x) // 新建立一个结点,这个结点是根据pos所建立,所以需要将他传递过来,也就是说当前新建立的结点是和pos对应的新结点, x是叶子结点要加1的
{
    int now = ++ cnt; // 开辟新节点
    tr[now] = tr[pos]; // 最初这个结点是完全和他所对应的结点
    tr[now].val += 1; // 这个新结点的孩子必然会多1,所以copy玩之后要加1
    if(l != r)
    {
        int mid = (l + r) >> 1;
        if(x <= mid) tr[now].l = update(tr[pos].l, l, mid, x);
        else tr[now].r = update(tr[pos].r, mid + 1, r, x);
        // 如果新的结点在叶子结点就不需要在新建立结点了,否则若是在左子树就改变新建立的结点的左子树,否则就改变新结点的右子树
    }
    return now; // 依然要返回
}
int query(int pos, int cur, int l, int r, int k) // 这个是查找区间第k大的操作,之前说过根据前缀和的性质我要将两颗线段树做差,不过实际上我只需要将一条链做差就行
{
    if(l == r) return l; // 如果找到叶子节点就一定是叶子节点对应的下标
    int num = tr[tr[cur].l].val - tr[tr[pos].l].val; // 我看只要看左子树的大小就可以知道我往左子树递归还是右子树递归, //这里的k是保证存在的,不然需要调用函数前加个if
    int mid = (l + r) >> 1;
    if(num >= k) return query(tr[pos].l, tr[cur].l, l, mid, k); // 要是num >= k那肯定会在左子树中
    return query(tr[pos].r, tr[cur].r, mid + 1, r, k - num); //否则的话肯定会在右子树中,并且这里要注意在右子树中代表这已经删除了num个比他排名低的,因此在右子树中找到排名就为k-num
}
<-这是注释开始->
首先对于原数可能需要离散化,
在求区间第k大的时候可以不用建树,但依然需要从root[1]开始,
要是建树就需要root[0] = build(1, n);
离线话时记得lower_bound后要+1因为权值线段树是根据1~n建立的而非0~n-1建立的
<-这是注释结束->
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注