kkogoro

主席树
主席树建议先了解权值线段树再来学习主席树什么是主席树是可持久化线段树的一种,主席树可以理解为可持久化权值线段树吧(...
扫描右侧二维码阅读全文
20
2018/10

主席树

主席树

建议先了解权值线段树再来学习主席树

什么是主席树

是可持久化线段树的一种,主席树可以理解为可持久化权值线段树(逃

什么是可持久化数据结构

保存了数据结构内数据经历变化过程中的各个历史版本,比如有一个数列a b c,我们依次给a,b,c加上1,那么我查询“第2次修改后序列的情况”我们需要给出序列a + 1, b + 1, c,这就叫查询历史版本,可能刚了解这个概念的同学会问这题离线不就行,但是可持久化数据结构是用来实现在线功能的

为什么叫主席树

因为提出它的人的名字首字母和我们的一位国家主席的一样(逃了逃了

如何实现

考虑暴力:保留历史版本,最暴力的方法自然是每次修改我们拷贝一份之前的整棵线段树

显然这种方法是不可行的,无论是时间还是空间

思考我们在哪里浪费资源了:回忆“权值线段树”一节提到的动态开点,动态开点的正确性基于我们每次修改一个节点的值,我们只会影响到根节点到这个节点的链上节点的值,而没有被我们修改到的节点的值和原来一样。

那么结论出来了:我们冗余复制了没有被改变的节点。

正解:每次修改只新建被修改影响到的节点,然后没有受到影响的节点,我们和之前的线段树共用同一片内存空间,如下图所示
编号1表示原线段树(为了方便演示,这个线段树是满的,但实际上它还是动态开出来的),

编号2的上图表示我们修改了最底层的红色节点,受到牵连的是编号2的下图中标红色的链,因此这条链欧我们新建出来,然后看那些“弯曲”的边,它们就是刚刚所说的和之前的线段树共用同一片内存空间,即我们把红色节点的未被修改的儿子直接指向上一个版本同位节点的等儿子

编号3的图大家自己体会一下

主席树

让我们来看一道经典例题

例题

洛谷P3834 【模板】可持久化线段树 1(主席树)

简要题意

给你一个 $n$ 个数的序列,没有修改, $m$ 次询问区间内排名为 $k$ 的元素是谁
$n<=1e5$, $m<=5e3$

求解

如果不考虑区间左端点是给定的,这题就是我在权值线段树一文中写的Problem_C.Hard问题,但是这道题需要我们精确到一个区间,考虑区间问题常见思想:前缀和思想

如果我们把一颗权值线段树内保存所有的元素的出现次数(权值)看作是一个状态(或者说是一维状态数组中的的一个元素),我们用把这些状态用一个数组存起来,每个状态表示序列中 $[1,\space i]$ 区间内元素出现次数,那么这个状态是满足区间可减性的,因为后一个状态是在前一个状态基础上转移而来,比如区间 $[1,\space i]$ 状态转移到区间 $[1,\space i+1]$ 状态,我们只是在权值线段树的 $num_{i+1}$ 处加了1。因此这个状态数组其实是状态前缀和,那么我们用 $[1,\space R]$ 状态 减去 $[1,\space L]$ 状态即可得到增量状态: $[L,\space R]$ 区间内数字的状态,然后对于这个状态我们只需要套用Problem_C.Hard的解法即可。

如何保存状态:使用一开始介绍的主席树从1到n计算状态前缀和的过程中就把各个前缀状态用主席树保存即可

当然POJ_2104上也是这道题,但是那个数据被削到different,无须去重,所以不在这里写了,
但是POJ那道对内存池大小要求相对精准一些,建议去过一下

细节

小优化

对于一些暂时用不到的空节点,我们先不开出来,在要用的时候用一个下放操作临时声明节点即可(或者可以像我一样判NULL

inline void push_down(Node* const &cur) {
    if (cur->ls == NULL) cur->ls = newNode();
    if (cur->rs == NULL) cur->rs = newNode();
    return;
}
关于内存开多大

如果采用普遍写法的对于0状态单独开一整棵树,空间复杂度应该精确到 $2*n\log n$个节点,因为需要一棵完整的空树和所有新链,如果你采用我这种对于空树的NULL特判,就开 $n\log n$ 个节点

需要注意的是 $\log n$ 不是严格的,我们可以使用程序测量或者开大一些 $\log n + 2$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 200007;


struct Chairman_Tree {
    struct Node {
        int val; //权值
        Node *ls, *rs; //左儿子,右儿子
    } node[MAXN * 18];   //2e5 * log(2e5),内存池
    int cntNode; //总节点数
    inline Node* newNode() { //从内存池申请新节点
        return &node[++cntNode];
    }
    
    inline void insert(const Node* const &pre, Node* &cur, const int &l, const int &r, const int &pos) { //插入节点,即建立新链
        cur = newNode(); //cur表示新的节点
        if (pre != NULL) *cur = *pre; //为了节省内存,不采用生成空节点方法,如果上一个历史版本的等节点非空,直接复制(原val,孩子指针)
        ++cur->val; //这里沿途更新即可,因为我们始终处在受影响的链上
        
        if (l == r) return;
        
        const int mid = (l + r) >> 1;
        //因为我们没有新建新节点,所以 千万 要对NULL做好特判
        if (pos <= mid) { 
            if (pre == NULL) insert(NULL, cur->ls, l, mid, pos);
            else insert(pre->ls, cur->ls, l, mid, pos);
        }
        else {
            if (pre == NULL) insert(NULL, cur->rs, mid + 1, r, pos);
            else insert(pre->rs, cur->rs, mid + 1, r, pos);
        }
        return;
    }
    
    inline int get_Lrank(const Node* const &cur) { //用于获得一个节点左儿子的size,注意判NULL
        return (cur == NULL || cur->ls == NULL) ? 0 : cur->ls->val;
    }
    inline int query(const Node* const &pre, const Node* const &cur, const int &l, const int &r, const int &aim) {
        int res = 0;
        if (l == r) { //到达叶子节点
            res = l;
        }
        else {
            const int mid = (l + r) >> 1;
            const int left_rank = get_Lrank(cur) - get_Lrank(pre); //状态前缀和作差获得增量信息
            if (left_rank >= aim) { 
                if (pre == NULL) res = query(NULL, cur->ls, l, mid, aim);
                else res = query(pre->ls, cur->ls, l, mid, aim);
            }
            else {
                if (pre == NULL) res = query(NULL, cur->rs, mid + 1, r, aim - left_rank);
                else res = query(pre->rs, cur->rs, mid + 1, r, aim - left_rank);
            }
        }
        return res;
    }
    
    Node* root[MAXN]; //保存各个历史版本的根
    inline void build(const int* const &num, const int &n, const int &length) {
        for (int i = 1; i <= n; ++i) { //在上一个版本基础上建立新版本
            insert(root[i - 1], root[i], 1, length, num[i]);
        }
        return;
    }
} tree;


int rank[MAXN], num[MAXN], tmp[MAXN]; //依次为大小排名,原数列,排序数列


int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        num[i] = read();
        tmp[i] = num[i];
    }
    
    std::sort(tmp + 1, tmp + 1 + n); //离散化过程
    const int length = std::unique(tmp + 1, tmp + 1 + n) - (tmp + 1);
    for (int i = 1; i <= n; ++i) {
        rank[i] = std::lower_bound(tmp + 1, tmp + 1 + length, num[i]) - tmp;
    }
    
    tree.build(rank, n, length); //注意要用length,不然建树过大费时废空间
    
    for (int i = 1; i <= m; ++i) { //回答询问
        int l = read(), r = read(), aim = read();
        int Rank = tree.query(tree.root[l - 1], tree.root[r], 1, length, aim);
        printf("%d\n", tmp[Rank]);
    }    
    return 0;
}
非递归query
inline int query(const Node *pre, const Node* cur, const int &length, int aim) {
    int l = 1, r = length;
    while (l < r) {
        const int mid = (l + r) >> 1;
        const int left_rank = get_Lrank(cur) - get_Lrank(pre); //状态前缀和作差获得增量信息
        if (left_rank >= aim) { 
            if (pre != NULL) pre = pre->ls;
            cur = cur->ls;
            r = mid;
        }
        else {
            if (pre != NULL) pre = pre->rs;
            cur = cur->rs;
            l = mid + 1;
            aim -= left_rank;
        }
    }
    return l;
}
非递归insert
inline void insert(Node** pre, Node** cur, const int &length, const int &pos) {
    int l = 1, r = length;
    while (l < r) {
        *cur = newNode();
        if (*pre != NULL) **cur = **pre;
        ++(*cur)->val;
        const int mid = (l + r) >> 1;
        if (pos <= mid) {
            if (*pre != NULL) pre = &(*pre)->ls;
            cur = &(*cur)->ls;
            r = mid;
        }
        else {
            if (*pre != NULL) pre = &(*pre)->rs;
            cur = &(*cur)->rs;
            l = mid + 1;
        }
    }    
    *cur = newNode();
    if (*pre != NULL) **cur = **pre;
    ++(*cur)->val;
    return;
}

洛谷P4137 Rmq Problem / mex

简要题意

给定序列,无修改,求区间mex。

序列长度 $2e5$ ,询问 $2e5$

求解

使用可持久化权值线段树(主席树),对每个下标 $pos$ 开一颗树维护每种下标在 $[1,pos]$ 范围内的权值最后一次出现的位置

询问区间 $[l,r]$ 转化为在第 $r$ 棵树上找第一个权值小于 $l$ 的位置。

细节

不能开严格的 $\log n$ 的空间, 使用程序测得最大深度为 $19$

#include <iostream>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 200007;


class ChairmanTreeNode {
    int lc, rc, val;
    friend class ChairmanTree;
} node[MAXN * 19];
int cntNode;
class ChairmanTree {
#define L(x) node[x].lc
#define R(x) node[x].rc
#define V(x) node[x].val
    private :
        int root[MAXN];
        inline int newNode() {
            ++cntNode;
            L(cntNode) = R(cntNode) = V(cntNode) = 0;
            return cntNode;
        }
        inline void copy(const int &pre, const int &cur) {
            node[cur] = node[pre];
            return;
        }
        void insert(const int &pre, int &cur, const int &l, const int &r, const int &aim, const int &val) {
            cur = newNode();
            if (pre != 0) copy(pre, cur);
            if (l == r) return (void)(V(cur) = val); 
            const int &mid = (l + r) >> 1;
            if (aim <= mid) insert(L(pre), L(cur), l, mid, aim, val);
            else insert(R(pre), R(cur), mid + 1, r, aim, val);
            V(cur) = std::min(V(L(cur)), V(R(cur)));
            return;
        }
        int query(const int &cur, const int &l, const int &r, const int &lim) {
            if (!cur || l == r) return l;
            const int &mid = (l + r) >> 1;
            if (V(L(cur)) < lim) return query(L(cur), l, mid, lim);
            else return query(R(cur), mid + 1, r, lim);
        }

    public :
        inline void build(int *data, const int &n) {
            for (int i = 1; i <= n; ++i) insert(root[i - 1], root[i], 0, n + 1, data[i], i);
            return;
        }
        inline int query(const int &n, const int &l, const int &r) {
            return query(root[r], 0, n + 1, l);    
        }
#undef L
#undef R
#undef V
} tree;


int data[MAXN];


int main() {
    int n = read();
    int m = read();
    for (int i = 1; i <= n; ++i) {
        data[i] = read();
        if (data[i] > n) data[i] = n + 1; //MAX_mex <= n
    }
    tree.build(data, n);
    while (m--) {
        int l = read();
        int r = read();
        printf("%d\n", tree.query(n, l, r));    
    }
    return 0;
}

深度测量

int build(int l, int r, int cost) {
    if (l == r) return cost;
    int mid = (l + r) >> 1;
    return std::max(build(l, mid, cost + 1), build(mid + 1, r, cost + 1));
}
Last modification:January 17th, 2019 at 01:16 pm

Leave a Comment