当前位置:   article > 正文

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

可持久化线段树

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

简介

可持久化线段树,又称主席树。对于普通的线段树,想要支持回退操作(Undo)十分困难。可持久化线段树应时而生,可持久化线段树可以支持在不同版本直接进行穿梭,修改和查询。

基本原理

以单点修改为例,对于一次单点修改创建一个新的版本,朴素的思路是将这个线段树从头到尾拷贝一份,但是拷贝操作不管是空间还是时间上的复杂度都是极高的。我们观察一下单点修改操作的修改过程。

原始线段树
我们把它变成圆形节点的形式:

线段树修改
其中,以橘色节点组成的路径即为修改路径,我们发现,只有修改路径上的节点的节点信息改变了,而其他节点的节点信息没有改变,这就是可持久化线段树的理论依据。

那么我们再创建新版本的时候,我们就可以只克隆修改路径上的节点,而不管其他节点。由于一条修改路径最多是 O ( log ⁡ N ) O(\log N) O(logN),因此不会改变线段树的时间复杂度。

节点克隆

可持久化线段树最关键的操作为节点克隆。例如上图,我们创建新版本的线段树为:

节点克隆

由图发现,我们只需要克隆修改路径上的节点,并且每一个新节点(橘色节点)都会指向一个新节点和一个旧节点。并且,根节点永远都会被克隆。

因此,每一个新的根节点都是一颗可独立操作的线段树,虽然和其他版本公用了一些节点,那么每个根节点都代表了一个时间版本的线段树

可持久化数组

主席树最简单的应用为可持久化数组。即,可以访问任意一个版本下的数组元素,也可以对任意一个版本进行单点修改。

P3919

数据结构

首先关于结构体的定义,在普通线段树的数据结构中,左右子节点的编号是可以通过根节点的编号算出来的。但是可持久化线段树却不具备这种完全二叉树的结构。因此,我们必须在结构体中存放孩子节点的编号信息。

struct Node
{
    int l;   // 左孩子节点编号
    int r;   // 右孩子节点编号
    int val; // 权值
} t[100000000];
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

并且附带一个 t o t tot tot全局变量,记录节点编号的分配信息。

int tot = 0;
  • 1

建树

建树过程很简单,注意该函数返回节点的编号,并且是边建树边建边的过程。 a r r arr arr数组为原始数组。调用完该函数获得初始版本的线段树。

int buildTree(int l, int r)
{
    int id = tot++; // 分配一个节点编号
    if (l == r - 1) // 如果是叶子节点,那么直接赋值
    {
        t[id].val = arr[l];
    }
    else // 否则就要递归建树
    {
        int mid = (l + r) >> 1;
        t[id].l = buildTree(l, mid);
        t[id].r = buildTree(mid, r);
    }
    return id; // 返回该节点的编号s
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

克隆节点

克隆节点作为一个工具函数,其作用为克隆一个节点出来,且节点信息不改变。

int clone(int i)
{
    int id = tot++;
    t[id] = t[i];
    return id;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

单点修改

单点修改时,修改路径上必须克隆出节点,并且递归修改,边修改边更改边的信息。

int update(int i, int l, int r, int idx, int val)
{
    i = clone(i); // 修改路径上必须克隆出节点
    if (l == r - 1) // 如果是叶子节点,那么就直接赋值即可
    {
        t[i].val = val;
    }
    else // 不是则递归修改
    {
        int mid = (l + r) >> 1;
        // 判断目标节点在左子树还是右子树,并将边指向新的克隆出来的节点
        if (idx < mid)
        {
            t[i].l = update(t[i].l, l, mid, idx, val);
        }
        else
        {
            t[i].r = update(t[i].r, mid, r, idx, val);
        }
    }
    return i; // 返回节点编号
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

单点查询

和普通的线段树没有区别。

int query(int i, int l, int r, int idx)
{
    if (l == r - 1) // 目标节点,直接返回
    {
        return t[i].val;
    }
    else // 递归查询
    {
        int mid = (l + r) >> 1;
        if (idx < mid)
        {
            return query(t[i].l, l, mid, idx);
        }
        else
        {
            return query(t[i].r, mid, r, idx);
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

版本系统

可持久化线段树需要一个版本管理系统。其中 r o o t root root数组,存放了不同版本编号下的根节点。

h e a d head head为版本头指针,永远指向最新版本。

其中 r o o t [ i ] root[i] root[i]将返回第 i i i个版本的线段树头指针。

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", arr + i);
    }

    int head = 0;                  // 版本头指针,永远指向最新版本
    root[0] = buildTree(1, n + 1); // 初始版本

    while (m--)
    {
        int vi, type;
        scanf("%d %d", &vi, &type);
        if (type == 1)
        {
            int idx, val;
            scanf("%d %d", &idx, &val);
            root[++head] = update(root[vi], 1, n + 1, idx, val); // 获得一个新版本
        }
        else
        {
            int idx;
            scanf("%d", &idx);
            int ans = query(root[vi], 1, n + 1, idx);
            root[++head] = clone(root[vi]); // 获得一个新版本,虽然什么也没有修改
            printf("%d\n", ans);
        }
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

代码

最后给出完整代码。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define FR freopen("in.txt", "r", stdin)
#define FW freopen("out.txt", "w", stdout)

struct Node
{
    int l;   // 左孩子节点编号
    int r;   // 右孩子节点编号
    int val; // 权值
} t[100000000];

int arr[2000005];
int root[2000005];
int tot = 0;

int n, m;

int buildTree(int l, int r)
{
    int id = tot++; // 分配一个节点编号
    if (l == r - 1) // 如果是叶子节点,那么直接赋值
    {
        t[id].val = arr[l];
    }
    else // 否则就要递归建树
    {
        int mid = (l + r) >> 1;
        t[id].l = buildTree(l, mid);
        t[id].r = buildTree(mid, r);
    }
    return id; // 返回该节点的编号s
}

int clone(int i)
{
    int id = tot++;
    t[id] = t[i];
    return id;
}

int update(int i, int l, int r, int idx, int val)
{
    i = clone(i);   // 修改路径上必须克隆出节点
    if (l == r - 1) // 如果是叶子节点,那么就直接赋值即可
    {
        t[i].val = val;
    }
    else // 不是则递归修改
    {
        int mid = (l + r) >> 1;
        // 判断目标节点在左子树还是右子树,并将边指向新的克隆出来的节点
        if (idx < mid)
        {
            t[i].l = update(t[i].l, l, mid, idx, val);
        }
        else
        {
            t[i].r = update(t[i].r, mid, r, idx, val);
        }
    }
    return i; // 返回节点编号
}

int query(int i, int l, int r, int idx)
{
    if (l == r - 1) // 目标节点,直接返回
    {
        return t[i].val;
    }
    else // 递归查询
    {
        int mid = (l + r) >> 1;
        if (idx < mid)
        {
            return query(t[i].l, l, mid, idx);
        }
        else
        {
            return query(t[i].r, mid, r, idx);
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", arr + i);
    }

    int head = 0;                  // 版本头指针,永远指向最新版本
    root[0] = buildTree(1, n + 1); // 初始版本

    while (m--)
    {
        int vi, type;
        scanf("%d %d", &vi, &type);
        if (type == 1)
        {
            int idx, val;
            scanf("%d %d", &idx, &val);
            root[++head] = update(root[vi], 1, n + 1, idx, val); // 获得一个新版本
        }
        else
        {
            int idx;
            scanf("%d", &idx);
            int ans = query(root[vi], 1, n + 1, idx);
            root[++head] = clone(root[vi]); // 获得一个新版本,虽然什么也没有修改
            printf("%d\n", ans);
        }
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120

有了可持久化数组,基于数组的数据结构都有了可持久化的版本,例如可持久化并查集,可持久化链表。

动态开点线段树

有时候,我们构造线段树的时候并不需要把所有的线段树的节点都构造出来,我们可以在有必要使用这个节点时候才去构造节点,过程类似于主席树。这样,可以减少线段树带来的空间问题。

百分之90的动态开点线段树都可以进行离散化+普通线段树。

例题

区间查询第K小

P3919

思路应用了前缀和思想,首先对数据进行离散化,维护离散序号区间 [ 1 , i d ] [1,id] [1,id]注意去重,每个槽就储存了该标号数字的个数,从数组从左到右进行插入,每次插入都创建一个新的线段树版本。

假如查询区间 [ l , r ] [l,r] [l,r]那么对应每一个节点 i d id id,用 r r r的版本减去 l − 1 l - 1 l1版本的数量即可得到该区间下的的数量。

然后根据区间内数字的数量选择左右子树即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define FR freopen("in.txt", "r", stdin)
#define FW freopen("out.txt", "w", stdout)

struct Node
{
    int l;
    int r;
    int val;
} t[5000005];

int root[200005];

int tot = 0;
int head = 0;

int buildTree(int l, int r)
{
    int id = tot++;
    if (l == r - 1)
    {
        t[id].val = 0;
    }
    else
    {
        int mid = (l + r) >> 1;
        t[id].l = buildTree(l, mid);
        t[id].r = buildTree(mid, r);
        t[id].val = 0;
    }
    return id;
}

int clone(int i)
{
    int id = tot++;
    t[id] = t[i];
    return id;
}

int insert(int i, int l, int r, int idx)
{
    i = clone(i);
    if (l == r - 1)
    {
        t[i].val++;
    }
    else
    {
        t[i].val++;
        int mid = (l + r) >> 1;
        if (idx < mid)
        {
            t[i].l = insert(t[i].l, l, mid, idx);
        }
        else
        {
            t[i].r = insert(t[i].r, mid, r, idx);
        }
    }

    return i;
}

int getKth(int a, int b, int l, int r, int k)
{
    if (l == r - 1)
    {
        return l;
    }
    else
    {
        int mid = (l + r) >> 1;
        int ln = t[t[b].l].val - t[t[a].l].val;
        int rn = t[t[b].r].val - t[t[a].r].val;
        if (ln >= k)
        {
            return getKth(t[a].l, t[b].l, l, mid, k);
        }
        else
        {
            return getKth(t[a].r, t[b].r, mid, r, k - ln);
        }
    }
}

int ori[200005];

int n, m;

int main()
{
    scanf("%d %d", &n, &m);

    set<int> st;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", ori + i);
        st.insert(ori[i]);
    }

    int id = 0;
    map<int, int> mp, vmp;
    for (auto it = st.begin(); it != st.end(); it++)
    {
        id++;
        mp[id] = *it;
        vmp[*it] = id;
    }

    root[0] = buildTree(1, id + 1);
    for (int i = 1; i <= n; i++)
    {
        root[i] = insert(root[i - 1], 1, id + 1, vmp[ori[i]]);
    }

    while (m--)
    {
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k);

        int val = getKth(root[l - 1], root[r], 1, id + 1, k);

        printf("%d\n", mp[val]);
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/180124
推荐阅读
相关标签
  

闽ICP备14008679号