主席树（可持久化线段树）

开始阅读之前，请确保您已完全理解普通线段树的工作原理。

思想：在线段树的基础上维护多个历史版本。

支持操作：在任意一个历史版本上的区间查询，基于任意一个历史版本的单点修改

关于区间修改：稍微想想可以得出两种处理方式：
1. 修改时暴力将所有修改的节点开出来，时间复杂度\(O(n)\)。这显然是无法承受的。
2. 打懒标记，访问到时（pushdown时）再将没有开的点现场开出来，时间近似\(O(\log_2n)\)。但是细节复杂，在此不做讨论。

0. 存储结构：和线段树没有区别。

struct node {
    int sum;
    int left, right;
    node* lson, *rson;
};

node* root[MaxN];
int vercnt = 1;
node mem[35 * MaxN], *memtop = mem;
#define ALLOCATE (++memtop)

1. 建树：和普通线段树没有区别。

void build(int left = 1, int right = n, node*& p = root[0]) {
    p = ALLOCATE;
    p->left = left;
    p->right = right;
    p->sum = 0; // 此处将初值全部置为零
    p->lson = p->rson = nullptr;
    if (left != right) {
        int mid = (left + right) / 2;
        build(left, mid, p->lson);
        build(mid + 1, right, p->rson);
    }
}

2. 单点修改分为以下几个步骤：（以区间和单点加为例）
（1）新建一个节点，将新节点左右边界、左右子均设为旧节点的对应值。
（2）如果当前节点的左右边界值相等：到达了目标位置，将新节点的区间（单点）和设为旧节点的区间（单点）和加上目标值之后直接返回。
（3）没有返回：判断目标位置在当前区间的左子还是右子，递归继续修改对应的节点，同时保持另一个节点不变（即沿用旧版本的对应节点）。
（4）递归返回后，当前区间的区间和一定改变，要更新这个值。

void _addpnt(int pos, int val, node*& cur, node* prev) {
    cur = ALLOCATE;                               // 步骤一
    cur->left = prev->left;
    cur->right = prev->right;
    cur->sum = prev->sum;
    cur->lson = prev->lson;
    cur->rson = prev->rson;

    if (prev->left == prev->right) {              // 步骤二
        cur->sum += val;
        return;
    }

    if (prev->lson->right >= pos)                 // 步骤三
        _addpnt(pos, val, cur->lson, prev->lson);
    else if (prev->rson->left <= pos)
        _addpnt(pos, val, cur->rson, prev->rson);

    cur->sum = cur->lson->sum + cur->rson->sum;   // 步骤四
}

int addpnt(int pos, int val) { // 返回新版本的版本编号
    _addpnt(pos, val, root[vercnt], root[vercnt - 1]);
    vercnt++;  // ↑传入对应的版本的根节点
    return vercnt - 1;
}

3. 区间查询和普通线段树没有区别。

int query(int left, int right, node* root) {
    /* 此处代码省略 */
}

注意到一个特性：主席树第N个版本的状态实质上是前N次修改相加的前缀和。所以我们可以通过比较两个版本状态的方式得出某两次修改之间的状态。

所以，主席树常常配合离散化来处理许多与区间值大小顺序有关的问题，如静态区间第K大/小。P3834 【模板】可持久化线段树 1（主席树）

套路处理方法：
1. 将所有值离散化。
2. 将所有值按照原数组顺序依次插入空的主席树中离散化后的位置。
求区间第K大时，取左开右闭区间两端的版本相比较，求整体第K大。

// (lver, rver]
int _get(int left, int right, int k, node* lver, node* rver) {
    if (lver->left == lver->right)
        return rver->val;
    int leftcnt = rver->lson->size - lver->lson->size;
    if (leftcnt >= k)
        return _get(left, lver->lson->right, k, lver->lson, rver->lson);
    else
        return _get(lver->rson->left, right, k - leftcnt, lver->rson, rver->rson);
}
// [left, right]
int getkth(int left, int right, int k) {
    return _get(1, n, k, root[left - 1], root[right]);
}

时间复杂度：建树\(O(n)\)，修改\(O(\log_2n)\)，区间查询\(O(\log_2n)\)

空间复杂度：建树\(O(n)\)，修改\(O(\log_2n)\)