您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

可持久化线段树 主席树 详解

😊 | Powered By HeartFireY | Persistent Segment Tree
📕 | 需要的前导知识:线段树(Segment Tree)、权值线段树、可持久化数据结构理论(Persistent Data Structure Theory)

一、可持久化线段树 简介

可持久化线段树,顾名思义,即对线段树进行可持久化处理之后的线段树。

在可持久化数据结构的理论中,我们对可持久化的概念有所了解:“可以返回之前的某个状态,并在该基础上进行修改”。可持久化线段树就是这样一种结构。

我们从一般思路出发进行分析:想要让线段树可持久化,最朴素的方法就是每进行一次操作都新建一颗线段树。但显然这是不明智的做法:时间和空间上而言都是非常差的的算法。我们不妨继续分析一下更新之后与更新之前的结构:每次更新都只有少量的点被修改。因此大量的点可以继续使用,无需重新建树。

本文分两个部分对可持久化线段树进行探讨。

值得注意的是:我们一般认为主席树就是可持久化线段树,实际上两者之间有区分:

可持久化线段树单纯指经过可持久化处理之后,能够查询、修改历史节点数据的结构,建立在基础线段树的基础之上;而主席树建立在权值线段树的基础之上,能够查询修改历史节点。二者本质区别在于纪念性可持久化的对象所维护的对象不同(一个维护权值、一个维护值域)。

因此,可持久化线段树 ≠ \neq =主席树,准确的说,主席树 ⊂ \subset 可持久化线段树。

二、可持久化线段树 基本结构与操作

1.基本结构、建树操作

首先应该明确一点:由于可持久化结构重叠的特殊性,可持久化线段树不能采用堆式储存,因此只能采取动态开点的方式进行储存。

不同于后续节点的更新,对于最初的状态下的线段树我们采用一次建树完成:

  1. 采用递归建树,递归函数参数保存左右边界(初始化为 ( 1 , n ) (1, n) (1,n))、当前元素的指针。同时保存总计数 c n t cnt cnt

  2. 递归边界控制为 l = = r l == r l==r,由于此时左边界 l l l即为指向 a a a数组的指针,因此叶子节点赋值 v a l ( p ) = a [ l ] val(p) = a[l] val(p)=a[l]

  3. 非叶子节点首先记录左右子节点的下标 l s ( p ) = c n t + + , r s ( p ) = c n t + + ls(p) = cnt++, rs(p) = cnt++ ls(p)=cnt++,rs(p)=cnt++,然后递归建左右子树:

    b u i l d ( l ,   m i d ,   l s ( p ) ) 、 b u i l d ( m i d + 1 , / r , r s ( p ) ) build(l,\ mid,\ ls(p))、build(mid + 1,/ r, rs(p)) build(l, mid, ls(p))build(mid+1,/r,rs(p))

  4. 建立左右节点后非叶子节点 = 左右子节点的和: v a l ( p ) = v a l ( l s ( p ) ) + v a l ( r s ( p ) ) val(p) = val(ls(p)) + val(rs(p)) val(p)=val(ls(p))+val(rs(p))

根据以上建树过程,我们以数组 a = 1 , 2 , 3 , 4 , 5 a = {1,2,3,4,5} a=1,2,3,4,5为例建立线段树:

在这里插入图片描述

可以看到:不同于基础线段树,可持久化线段树的下标不再遵循堆的规律,这种建树方式我们称为动态开点

结构体封装版:

#define ls(x) tree[x].ls
#define rs(s) tree[x].rs
#define val(x) tree[x].val
#define mark(x) tree[x].mark
struct node{
    int val, mark = INT_MIN;
    int ls, rs;
}tree[MAXN];

void build(int l = 1, int r = n, int p = 1){
    if(l == r) val(p) = a[l];
    else{
        ls(p) = ++cnt, rs(p) = ++cnt;
        int mid = (l + r) >> 1;
        build(l, mid, ls(p));
        build(mid + 1, r, rs(p));
        val(p) = val(ls(p)) + val(rs(p));
    }
}

建树完毕后,上述线段树已经静态化,后续的修改操作通过增加新节点来实现。

2.单点修改

假设现在要对 A [ 4 ] A[4] A[4] − 2 -2 2,则操作步骤如下:

首先建立新根结点,更新根节点记录数组: r o o t [ f l a g ] = + + c n t root[flag] = ++cnt root[flag]=++cnt

在这里插入图片描述

创建新节点后对其进行处理。由于我们要修改的元素 A [ 4 ] A[4] A[4]位于右子树,因此左子树部分保持不变,可以继续使用。因此将原左子树与新节点相连,同时新建右子节点。

在这里插入图片描述

继续处理, A [ 4 ] A[4] A[4]位于当前结点左子树,右子树保持不变继续使用,因此新建左子节点,将原右子节点与新节点相连。

继续访问左子节点发现到达叶子结点,对原数据进行处理后再逐层回溯,更新路径上的结点值。

在这里插入图片描述

单点修改的操作到此结束。可以看到,对于最初版本的线段树,其任何数据未被改变。

void update(int x, int d, int p, int q, int cl = 1, int cr = n){
    if (cl == cr) val(q) = val(p) + d; // 给叶子节点赋值
    else{
        ls(q) = ls(p), rs(q) = rs(p); // 复制节点
        int mid = (cl + cr) / 2;
        if (x <= mid) ls(q) = ++cnt, update(x, d, ls(p), ls(q), cl, mid); 
        // 创建新节点作为左儿子,然后往左递归
        else rs(q) = ++cnt, update(x, d, rs(p), rs(q), mid + 1, cr); 
        // 创建新节点作为右儿子,然后往右递归
        val(q) = val(ls(q)) + val(rs(q)); // 根据子节点给当前节点赋值
    }
}

3.区间查询

区间查询与基础线段树几乎一致,只需要额外关注查询的版本对应的根节点即可。

int query(int l, int r, int p, int cl = 1, int cr = n){
    if (cl > r || cr < l) return 0;
    else if (cl >= l && cr <= r) return val(p);
    else{
        int mid = (cl + cr) / 2;
        return query(l, r, ls(p), cl, mid) + query(l, r, rs(p), mid + 1, cr);
    }
}

4.区间修改

我们需要再次回到 L a z y Lazy Lazy标记上进行讨论:

对于 L a z y Lazy Lazy标记,我们其实有两种实现方案:

  1. 标记上下传,也就是我们最常用的 p u u s h _ u p 、 p u s h _ d o w n puush\_up、push\_down puush_uppush_down操作;
  2. 标记永久化:标记时不用 p u u s h _ u p 、 p u s h _ d o w n puush\_up、push\_down puush_uppush_down,而是在查询的时候干预数据。

二者的一大区别在于,标记上下传会引发修改结点路径上的点的更新,而标记永久化不会影响树上的点。

这点区别是非常有意义的:考虑一棵可持久化线段树,如果从某节点上传,则到根节点路径上的点都会被修改,而可持久化结构导致了某些结点的复用,这会引发多个版本的线段树更新,无法指定是哪一版本;同理,下传标记也会引发不必要的点的更新。因此,我们只能通过标记永久化对可持久化线段树进行修改。

于是,我们在查询时需要额外带上一个标记:

ll query(int l, int r, int p, int cl = 1, int cr = n, ll mk = 0){
    if (cl > r || cr < l) return 0;
    else if (cl >= l && cr <= r) return val(p) + mk * (cr - cl + 1); // 加上带的标记
    else{
        int mid = (cl + cr) >> 1;
        return query(l, r, ls(p), cl, mid, mk + mark(p)) + query(l, r, rs(p), mid + 1, cr, mk + mark(p)); // 带着标记传递
    }
}

对于 u p d a t e update update操作,由于缺少传递标记,因此由子节点给当前节点赋值可能会发生错误。

void update(int l, int r, int d, int p, int q, int cl = 1, int cr = n){
    ls(q) = ls(p), rs(q) = rs(p), mark(q) = mark(p); // 复制节点
    if (cl >= l && cr <= r && cr > cl) mark(q) += d;
    else{
        int mid = (cl + cr) >> 1;
        if (cl <= r && mid >= l) ls(q) = ++cnt, update(l, r, d, ls(p), ls(q), cl, mid);// 提前进行判断,以免新建不必要的节点
        if (mid + 1 <= r && cr >= l) rs(q) = ++cnt, update(l, r, d, rs(p), rs(q), mid + 1, cr);
            
    }
    val(q) = val(p) + (min(cr, r) - max(cl, l) + 1) * d; // 根据需要更新的区间长度计算当前节点的值
}

三、主席树

区别于一般的可持久化线段树,主席树是可持久化权值线段树。

下面简单介绍一下主席树的构造过程:

1.建立空树

void build(int l = 1, int r = n, int p = 1){
    val(p) = 0;
    if (l != r){
        ls(p) = ++cnt, rs(p) = ++cnt;
        int mid = (l + r) / 2;
        build(l, mid, ls(p));
        build(mid + 1, r, rs(p));
    }
}

待补充


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进