P3834 【模板】可持久化线段树 1（主席树）

- 日理万妓 2021-11-13 23:20 253阅读 0赞

主席树 菜鸡看了一个晚上的时间才懂。 感觉网上的博客大都大乱。我也是找到了几遍好一点的看了一下。

参考博客：[https://blog.csdn.net/bestFy/article/details/78650360][https_blog.csdn.net_bestFy_article_details_78650360]  
参考博客：[https://blog.csdn.net/williamsun0122/article/details/77871278][https_blog.csdn.net_williamsun0122_article_details_77871278]  
题目链接：[https://www.luogu.org/problem/P3834][https_www.luogu.org_problem_P3834]

首先，会主席树的前提是会线段树。  
还有，我们一般在用线段树的时候，下标位置大都是采用了i \* 2 和i\* 2 + 1来作为i号的左右孩子。但是，在主席树中，我们不可以把这种思想带过来。因为主席树的是又多个线段树构成，那么也就是说每个节点的左右孩子都是会被重复利用的。我们如果用i*2 和i* 2 + 1来考虑，那就gg了。

所以，我们要先了解线段树的动态开点。这个其实也很简单。  
他把左右孩子的结点分别用L数组和R数组来进行保存。如果需要增加一个结点，那么就直接把下标值加1了。

同时，主席树是由多颗线段树组成的，至于为啥这样，还请看我安利的第一遍博客，有详细图解。

具体结合代码讲解：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int N,M;
    //T数组保存的是每颗线段树的根结点 sum数组保存的是以每个结点为根的树，里面数字的数量
    int T[200010],L[20 * 200010],R[20 * 200010],sum[20 * 200010],top;
    int a[200010],b[200010];
    
    void Build_Tree(int &root,int l,int r)
    {
        root = ++ top;//动态开点
        sum[root] = 0;
        int mid = (l + r) >> 1;
        if(l < r)
        {
            Build_Tree(L[root],l,mid);
            Build_Tree(R[root],mid + 1,r);
        }
    }
    
    void Update(int &root,int root1,int l,int r,int x)
    {
        root = ++ top;
        L[root] = L[root1];
        R[root] = R[root1];
        sum[root] = sum[root1] + 1;
        int mid = (l + r) >> 1;
        if(l >= r) return ;//一定要加这个，否则会出错，同时这个也容易忘记
        if(x > mid)
            Update(R[root],R[root1],mid + 1,r,x);
        else
            Update(L[root],L[root1],l,mid,x);
    }
    
    int Query(int u,int v,int l,int r,int x)
    {
        int num = sum[L[v]] - sum[L[u]];
        int mid = (l + r) >> 1;
        if(l >= r) return l;
        if(x <= num)
        {
            return Query(L[u],L[v],l,mid,x);
        }
        else
            return Query(R[u],R[v],mid + 1,r,x - num);
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= N; i ++)
        {
            scanf("%d",&a[i]); b[i] = a[i];
        }
        sort(b + 1,b + 1 + N);
        int m = unique(b + 1,b + 1 + N) - b - 1;
        Build_Tree(T[0],1,m);
        for(int i = 1; i <= N; i ++)
        {
            int t = lower_bound(b + 1,b + 1 + m,a[i]) - b;
            Update(T[i],T[i - 1],1,m,t);
        }
        while(M --)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            int t = Query(T[x - 1],T[y],1,m,z);
            printf("%d\n",b[t]);
        }
    }

[https_blog.csdn.net_bestFy_article_details_78650360]: https://blog.csdn.net/bestFy/article/details/78650360
[https_blog.csdn.net_williamsun0122_article_details_77871278]: https://blog.csdn.net/williamsun0122/article/details/77871278
[https_www.luogu.org_problem_P3834]: https://www.luogu.org/problem/P3834