算法竞赛模板

(模板)可持久化线段树 2
一个经典主席树的问题， 查询[\L,R]区间中第k小的数

先想更简单的问题，查询一次[1,n]中第k大的数
用线段树可以解决
对离散化后的数组构建权值线段树，即每个节点存到值是离散化后的数出现的次数和
二分，如果当前的区间次数和<=k,往左查 >k 往右找右边区间第 k - (左边区间) 大

主席树就是再[1,i]上建立n棵线段树，
发现前缀和的性质,第[L,R]区间的线段树可以通过[1,R] - [1,L-1]上相减得到

如何相减？在查询时，每到一个节点可以用减去对应的第L-1棵线段树对应的节点得到
O(1) 的复杂度对查询复杂度没有影响， 仍为O(logn)

开始时0号数先建立一个空的线段树
新增节点建新树时，都是从底到根增加一条新的节点，然后共用没有影响的节点，空间大概开20倍

#include <bits/stdc++.h>
using namespace std;

struct PresidentTree
{
    static constexpr int N = 2e5 + 10;
    int cntNodes = 0, root[N]; // root[i] 表示前i个元素构成的版本
    struct Node
    {
        int l = 0, r = 0; // 左右子节点编号（初始为0）
        int cnt = 0;      // 当前区间的元素个数
    };
    vector<Node> tr;

    PresidentTree() { tr.resize(20 * N); }

    // 构建初始空树
    void build_empty(int &u, int l, int r)
    {
        u = ++cntNodes;
        tr[u] = Node();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build_empty(tr[u].l, l, mid);
        build_empty(tr[u].r, mid + 1, r);
    }

    // 插入数值 x，返回新版本的根
    void modify(int &u, int v, int l, int r, int x)
    {
        u = ++cntNodes;
        tr[u] = tr[v];
        tr[u].cnt++;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        if (x <= mid)
            modify(tr[u].l, tr[v].l, l, mid, x);
        else
            modify(tr[u].r, tr[v].r, mid + 1, r, x);
    }

    // 查询第k小
    int kth(int u, int v, int l, int r, int k)
    {
        if (l == r)
            return l;
        int left_cnt = tr[tr[v].l].cnt - tr[tr[u].l].cnt;
        int mid = (l + r) >> 1;
        if (k <= left_cnt)
            return kth(tr[u].l, tr[v].l, l, mid, k);
        else
            return kth(tr[u].r, tr[v].r, mid + 1, r, k - left_cnt);
    }
};

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n + 1); 

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }

    // 离散化,排序去重
    sort(b.begin() + 1, b.end());
    auto ed = unique(b.begin() + 1, b.end());
    int m = ed - (b.begin() + 1); 

    PresidentTree tree;
    tree.build_empty(tree.root[0], 1, m); // 初始空树 root[0]

    // 构建前缀版本：遍历 a[1..n]
    for (int i = 1; i <= n; ++i) {
        int x = lower_bound(b.begin() + 1, ed, a[i]) - (b.begin() + 1) + 1;
        tree.modify(tree.root[i], tree.root[i - 1], 1, m, x);
    }

    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int rank = tree.kth(tree.root[l - 1], tree.root[r], 1, m, k);
        cout << b[rank] << "\n";
    }

    return 0;
}

模板】可持久化线段树 1

这个更水，开始时0号树用原数组建立线段树
其他新增版本操作类似，但是其实只用到了底部的节点
中间的节点只是充当了记录左儿子右儿子桥梁的作用

#include <bits/stdc++.h>
using namespace std;

struct PresidentTree
{
    static constexpr int N = 2e6 + 10;
    int cntNodes = 0, root[N]; // root[i] 表示前i个元素构成的版本
    struct Node
    {
        int l = 0, r = 0; // 左右子节点编号（初始为0）
        int cnt = 0;      // 当前区间的元素个数
    };
    vector<Node> tr;

    PresidentTree(vector<int>& a,int _n) { 
        tr.resize(20 * N);
        build_empty(root[0],1,_n,a);
    }

    // 构建初始空树
    void build_empty(int &u, int l, int r, vector<int>& a)
    {
        u = ++cntNodes;
        tr[u] = Node();
        if (l == r) {
            tr[u].cnt = a[l];
            return;
        }
            
        int mid = (l + r) >> 1;
        build_empty(tr[u].l, l, mid, a);
        build_empty(tr[u].r, mid + 1, r, a);
    }

    // 插入数值 x，返回新版本的根
    void modify(int &u, int v, int l, int r, int x, int val)
    {
        u = ++cntNodes;
        tr[u] = tr[v];
        if (l == r) {
            tr[u].cnt = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            modify(tr[u].l, tr[v].l, l, mid, x, val);
        else
            modify(tr[u].r, tr[v].r, mid + 1, r, x, val);
    }
    void copy(int &u, int v) {
        u = ++cntNodes;
        tr[u] = tr[v];
    }
    // 查询k位置
    int kth(int v, int l, int r, int k)
    {
        if (l == r) {
            return tr[v].cnt;
        }
        int mid = (l + r) >> 1;
        if (k <= mid)
            return kth(tr[v].l, l, mid, k);
        else
            return kth(tr[v].r, mid + 1, r,k);
    }
};

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    PresidentTree tree(a,n);

    
    for (int i = 1; i <= q; i++) {
        int v, op, p, val;
        cin >> v >> op >> p;
        if (op == 1) {
            cin >> val;
            tree.modify(tree.root[i],tree.root[v],1,n,p,val);
        } else {
            cout << tree.kth(tree.root[v],1,n,p) << '\n';
            tree.copy(tree.root[i],tree.root[v]);
        }
    }


    return 0;
}