精华内容
下载资源
问答
  • 权值线段树和主席树入门PPT,权值线段树,顾名思义就是记录权值的线段树,普通的线段树直接以坐标为l,r建树,而权值线段树是以大小来建树,树上寸的信息是该权值的数量,而通过建树时二分从小到大的性质,可以用这...
  • 一、权值线段树 简介 1.线段树 线段树是一种用于维护区间信息的高效数据结构,可以在 O(log⁡N)O(\log N)O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。...
    😊 | Powered By HeartFireY | Weighted Segment Tree

    一、权值线段树 简介

    1.线段树

    线段树是一种用于维护区间信息的高效数据结构,可以在 O ( log ⁡ N ) O(\log N) O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。

    线段树维护的信息必须满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用Lazy标记时,标记也要满足可加性

    具体有关线段树的的讲解请参考博客:线段树 详解与模板

    2.权值线段树

    权值线段树是一种建立在基本线段树之上的数据结构。因此它的基本原理仍是基于对区间的维护操作。但与线段树相区分的点是:权值线段树维护的信息与基本线段树有所差异:

    • 基本线段树中每个系欸但用来维护一段区间的最大值或总和等;
    • 权值线段树每个结点维护的是一个区间的数出现的次数。

    实际上,权值线段树可以看作是一个桶,桶的操作它都支持,并且能够以更快的方式去完成。

    根据权值线段树的性质,我们可以知道其主要用途:

    权值线段树一般用于维护一段区间的数出现的次数,从它的定义来看,它可以快速计算出一段区间的数的出现次数。

    在实际应用中,我们使用权值线段树查询区间第 K K K大的值。

    二、权值线段树的基本原理与操作

    1.权值线段树维护信息的原理

    基础线段树和权值线段树的一个较大的区别点在于:(此处特指使用数组储存树结构)基础线段树根据初始的一个序列建立树结构,具有单独的建树操作;而权值线段树不需要进行建树操作,初始状态下默认建立一棵所有点权为 0 0 0的空树,对于每个元素,在遍历的时候相应的结点做自增运算。换而言之:

    • 权值线段是一棵已经建好的线段树,储存树结构的下标范围根据区间最大值最小值确定(一般开大空间即可);
    • 初始状态下所有的点权均为 0 0 0
    • 执行插入元素的操作时,会导致插入值 v v v对应的 A [ v ] + + A[v]++ A[v]++,同时引发单点更新操作。
    • 可以从上述描述中得到基本推论:向空的权值线段树中插入一个无序序列,则插入完成后在树上无法再得到原序列的遍历,但能通过遍历得到有序序列(无序序列变有序序列)

    我们可以通过结构对比线段树与权值线段树的区别,以此理解原理。

    我们给定序列 { 1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 } \{1, 2, 2, 3, 3, 3, 4, 4, 4, 4 \} {1,2,2,3,3,3,4,4,4,4},以该序列为例建立两种线段树。

    首先,序列长度为 10 10 10,建立基础区间和查询线段树,结构图如下:

    在这里插入图片描述

    对应具体的细节不再阐述。我们继续建立权值线段树:首先给出一棵空树:

    (注:为演示方便,A数组下标做+1操作,树上的范围也对应变化,这里懒得改了~)

    在这里插入图片描述

    然后按照序列顺序插入元素:

    在这里插入图片描述

    解释:

    A [ 1 ] = 1 A[1] = 1 A[1]=1:原序列中存在值为 1 1 1的元素 1 1 1
    A [ 2 ] = 1 A[2] = 1 A[2]=1:原序列中存在值为 2 2 2的元素 2 2 2
    A [ 3 ] = 1 A[3] = 1 A[3]=1:原序列中存在值为 3 3 3的元素 3 3 3
    A [ 4 ] = 1 A[4] = 1 A[4]=1:原序列中存在值为 4 4 4的元素 4 4 4

    D [ k ] D[k] D[k]一定区间内所含元素的个数

    我们继续探究查找第 K K K大元素的方法:

    由于权值线段树每个节点记录了某段区间内包含的元素个数,且元素在叶子节点构成的序列中是有序的:

    • 对于整列数中第 K K K大/小的值,我们从根节点开始判断(这里按第 K K K大为例),如果 K K K比右儿子大,就说明第 K K K大的数在左儿子所表示的值域中。然后, K K K要减去右儿子。(这是因为继续递归下去的时候,正确答案,整个区间的第 K K K大已经不再是左儿子表示区间的第 K K K大了)。如此递归到叶子节点时即为答案。
    • 整棵线段树的根节点就表示整个值域有几个数。

    我们很容易看出:在权值线段树中,采用元素到下标数组映射的方式进行插入。这样会导致一个问题:在数据离散程度较大的情况下,空间的利用效率比较低。因此我们对于线段树所开空间不足时,常采用离散化的方式进行解决。

    📕 | 此处的前导知识:离散化(具体的参见离散化的讲解)

    2.权值线段树的基本操作与实现

    ①.查询第 K K K大/小元素

    假设 K = 5 K = 5 K=5,那么查询过程是怎样的?

    首先我们从根节点出发,由于要查询第 K K K大,是相对于终点而言的,因此从右子结点开始判断:

    在这里插入图片描述

    当前节点右子树包含 4 4 4个元素,所以应该向左子树遍历,注意:此时应该减去右子树的 4 4 4个元素!

    在这里插入图片描述

    寻找第 K K K小的操作与上方类似,区别在于相对于起点OR终点而言(遍历时对左右子树的判断顺序)。

    再次回顾整个步骤:对于整列数中第 K K K大/小的值,我们从根节点开始判断(这里按第 K K K大为例),如果 K K K比右儿子大,就说明第 K K K大的数在左子树中。然后, K K K要减去右子节点的值。(这是因为继续递归下去的时候,正确答案,整个区间的第 K K K大已经不再是左子树表示区间的第 K K K大了)。如此递归到叶子节点时即为答案

    根据以上分析步骤,我们可以写出查询第 K K K大和第 K K K小的函数:

    int query_kth(int pos, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1, right = tree[pos << 1 | 1];
        if(k <= right) return query(pos << 1 | 1, mid + 1, r, k);
        else return query(pos << 1, l, mid, k - right);
    }
    
    int query_kth(int pos, int l, int r, int k){
        if(l == r) return l;
        int mid = (l + r) >> 1, left = tree[pos << 1];
        if(k <= left) return query(pos << 1, l, mid, k - left);
        else return query(pos << 1 | 1, mid + 1, r, k);
    }
    

    ②.单点更新操作

    类似基础线段树,递归到叶子节点 + 1 +1 +1然后回溯

    void add(int l, int r, int v, int x){
        if (l == r) tree[v]++;
        else{
            int mid = (l + r) >> 1;
            if (x <= mid) add(l, mid, v << 1, x);
            else add(mid + 1, r, v << 1 | 1, x);
            tree[v] = tree[v << 1] + tree[v << 1 | 1];
        }
    }
    

    ③.查询某个数出现的个数

    树上二分查找的思想,代码如下:

    int find(int l, int r, int v, int x){
        if (l == r) return tree[v];
        else{
            int mid = (l + r) >> 1;
            if (x <= mid) return find(l, mid, v << 1, x);
            else return find(mid + 1, r, v << 1 | 1, x);
        }
    }
    

    ④.查询一段区间的数出现的次数

    int find(int l, int r, int v, int x, int y){
        if (l == x && r == y) return tree[v];
        else{
            int mid = (l + r) >> 1;
            if (y <= mid) return find(l, mid, v << 1, x, y);
            else if (x > mid) return find(mid + 1, r, v << 1 | 1, x, y);
            else return find(l, mid, v << 1, x, mid) + find(mid + 1, r, v << 1 | 1, mid + 1, y);
        }
    }
    

    3.区间离散化

    如前所述,在将元素个数映射到叶子节点的过程中,离散程度较大时会导致极低的空间利用效率。对本种数据结构,我们关心的仅仅是元素之间的大小关系,因此可以采用离散化的方法对空间进行优化。

    离散化的知识在此不展开赘述,直接采用C++STL算法

    int get_discretization(){
        for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i]; //读入数据
        sort(b + 1, b + n + 1);
        int len = unique(b + 1, b + n + 1) - b - 1;
        for (int i = 1; i <= n; ++i){
            int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
            a[i] = pos;
        } //离散化
    }
    
    展开全文
  • 权值线段树

    2018-08-14 08:25:47
    权值线段树 简介 维护全局的值域信息,每个节点记录的是该值域的值出现的总次数。 使用二分的思想(离散化的时候,需要用到) 支持查询全局K小值,全局rank,前驱,后继等。 单词操作时间复杂度为O(logn) 空间...

    权值线段树

    简介

    1. 维护全局的值域信息,每个节点记录的是该值域的值出现的总次数。
    2. 使用二分的思想(离散化的时候,需要用到)
    3. 支持查询全局K小值,全局rank,前驱,后继等。
    4. 单词操作时间复杂度为O(logn)
    5. 空间复杂度为O(n)
    6. 相对于平衡树的优势:代码简单,速度快
    7. 劣势:值域较大时,我们需要离散化,变成离线数据结构(我认为的离线指的是不能更改插入之类的操作,只能进行查询)

    例题

    1. 求解逆序对的个数(树状数组,归并排序等等方法)
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int maxn=5005;
    struct node
    {
        int l,r,num;
    }data[4*maxn];
    void build(int id,int l,int r)
    {
        data[id].l=l;
        data[id].r=r;
        data[id].num=0;
        if(l==r)
            return ;
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
    }
    int query(int id,int l,int r)
    {
        if(data[id].l==l&data[id].r==r)
            return data[id].num;
        int mid=(data[id].l+data[id].r)/2;
        if(mid>=r)
            return query(id*2,l,r);
        else if(mid<l)
            return query(id*2+1,l,r);
        else
            return query(id*2,l,mid)+query(id*2+1,mid+1,r);
    }
    void update(int id,int x)
    {
        if(data[id].l==x&&data[id].r==x)
        {
            data[id].num++;
            return ;
        }
        int mid=(data[id].l+data[id].r)/2;
        if(mid>=x)
            update(id*2,x);
        else
            update(id*2+1,x);
        data[id].num=data[id*2].num+data[id*2+1].num;
        return ;
    }
    int a[maxn];
    int main()
    {
        int n;
        while(cin>>n)
        {
            build(1,1,n+1);
            int ans=0,x;
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                a[i]++;
                ans+=query(1,a[i]+1,n+1);
                update(1,a[i]);
            }
            int sum=ans;
            for(int i=n-1;i>=0;i--)
            {
                ans=ans-(n-a[i])+(a[i]-1);
                sum=min(sum,ans);
            }
            cout<<sum<<endl;
        }
        return 0;
    }

    总而言之,权值线段树就是指每个节点存的是这个点出现的次数。
    比如对于1,3,4,5,5,6;
    画出一棵树

    这里写图片描述
    最底下的节点数从1到n,有n个,如果为0的节点数太多,我们需要离散化,因为压根没有用到,不需要。
    其次根节点的权值等同于序列中该值出现的次数。
    权值线段树感觉考的东西比较少,介绍这个主要是为了介绍主席树(可持久化线段树),为了理解主席树。

    主席树

    离散化

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int a[100],b[100],c[100],n;
    int solve()//离散化
    {
        for(int i=0;i<n;i++) b[i]=a[i];
        sort(b,b+n);
        int m=unique(b,b+n)-b;//去重
        for(int i=0;i<n;i++) c[i]=lower_bound(b,b+m,a[i])-b;//二分找对应位置
        for(int i=0;i<n;i++) printf("%d ",c[i]);
    }
    int main()
    {
    
        freopen("in.txt","r",stdin);
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        solve();
        return 0;
    }

    1. B站关于权值线段树的视频https://www.bilibili.com/video/av16552942
    2. 权值线段树代码实现 https://blog.csdn.net/tianyuhang123/article/details/77975426
    展开全文
  • 这篇的重点是为各位简绍主席的知识,当然在减少主席之前,还需要一些准备知识 第一:离散化 离散化: 把无限空间有限个体映射到有限空间里有限 白话:在不改变数据相对大小的条件下,对数据进行相应的缩小 例如: ...

    这篇的重点是为各位简绍主席树的知识,当然在简绍主席树之前,还需要一些准备知识
    第一:离散化
    离散化:
    把无限空间有限个体映射到有限空间里有限
    白话:在不改变数据相对大小的条件下,对数据进行相应的缩小
    例如:
    原数据:7 1 4 3处理后:4 1 3 2
    原数据:{100,250}{200,400}处理后{1,3}{2,4}
    离散化需要函数:unique函数(去重函数)
    low_bound(x,y,val)函数:
    在(x,y)范围内返回>=val的第一个元素位置。如果所有元素都小于val,则返回last的位置
    所谓离散化,就是为了防止当数字绝对值过大是,我们的线段树无法开出那么大的数组,同时降低我们的空间复杂度和时间复杂度。
    下面是两种常见的离散化方法(个人推荐第一种,更为简单)
    第一种:

    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    using namespace std;
    #define maxl 1000;
    //n原数组的大小
    //num原数组的中的元素
    //lsh离散化的数组
    //cnt离散化后的大小
    int lsh[maxl],n,num[maxl],cnt;
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>num[i];
    		lsh[i]=mun[i];
    	}
    	sort(lsh+1,lsh+n+1);
    	cnt=unique(lsh+1,lsh+n+1)-lsh-1;
    	for(int i=1;i<=n;i++)
    		num[i]=lower_bound(lsh+1,lsh+cnt+1,num[i])-lsh;
    }
    

    第二种:

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    #define maxl 100;
    struct node
    {
        int data,id;
        bool operator<(const node &a) const
        {
            return data < a.data;
        }
    };
    int main()
    {
        node num[maxl];
        int rankl[maxl];
        int n=100;
        for(int i=1;i<=n;i++)
        {
            cin>>num[i].data;
            num[i].id=i;
        }
        sort(num+1,num+n+1);
        for(int i=1;i<=n;i++)
            rankl[num[i].id]=i;
    }
    

    第二种:权值线段树
    权值线段树(一般用结点式存储struct node{int sumv,lc,rc;};) 😕/一定要是全局的!!!
    1、维护全局的值域信息,每个结点记录的其实是该值域的值出现的总次数
    2、用了二分的思想
    3、支持查询全局K小值,全局rank,前驱,后继等
    (前驱:小于x,且最大的数 后继:大于x,且最小的数)
    4、单次操作时间复杂度O(log(n))
    5、空间复杂度O(n)
    6、相对于平衡二叉树的优势:代码简单、速度快
    7、劣势:值域较大(10^9)??时,需要离散化,就变成了离线数结构
    okk那我们接下来就来讲解权值线段树的代码
    //插入删除

    int tree[n<<2];
    void update_tree(int p,int v,int rt,int l,int r)//当v=1为增加,当v=-1的时为减少
    {
    	tree[rt]+=v;
    	if(l==r)
    		return;
    	int mid=(l+r)>>1;
    	if(p<=m)
    		update_tree(p,v,rt<<1,l,mid);
    	else
    		update_tree(p,v,rt<<1|1,mid+1,r);
    }
    

    //k小值

    int kth(int k,int rt,int l,int r)
    {
    	if(l==r)
    		return l;
    	int mid=(l+r)>>1;
    	if(tree[rt<<1]>=k)
    		return kth(k,rt<<1,l,mid);
    	else
    		return kth(k-tree[rt<<1],rt<<1|1,mid+1,r);
    }
    

    排名(即区间和查询)

    int rankl(int p,int rt,int l,int r)
    {
    	if(r<p)
    		return tree[rt];
    	int mid=(l+r)>>1;
    	int res=0;
    	res+=rankl(p,rt<<1,l,m);
    	if(m<p-1)
    		res+=rankl(p,rt<<1|1,m+1,r);
    	return res;
    }
    

    在求排名的代码中,if和else的判断会显得有些不同,我们在函数中对于左子树的递归无需进行条件的判断,因为,我们排名默认为从左向右递增,所以我们只需要判断是否到达所求的叶子节点和是否需要向右子树进行递归。

    前驱

    int rankl(int p,int rt,int l,int r)
    {
        if(r<p)
            return t[rt];
        int m=(l+r)>>1;
        int res=0;
        res+=rankl(p,rt<<1,l,m);
        if(m<p-l)
            res+=rankl(p,rt<<1|1,m+1,r);
        return res;
    }
    //前驱
    int findl(int rt,int l,int r)
    {
        if(l==r)
            return l;
        int m=(l+r)>>1;
        if(t[rt<<1|1])
            return findl(rt<<1|1,m+1,r);
        return findl(rt<<1,l,m);
    }
    int pre(int p,int rt,int l,int r)
    {
        if(r<p)
        {
            if(t[rt])
                return findl(rt,l,r);//查询最靠右的数
            return 0;
        }
        int m=(l+r)>>1;
        int re;
        if(m<p-1&&t[rt<<1|1]&&(re=pre(p,rt<<1|1,m+1,r)))//先考虑右子树
            return re;
        return pre(p,rt<<1,l,m);
    }
    

    后继

    int findl(int rt,int l,int r)
    {
        if(l==r)
            return l;
        int m=(l+r)>>1;
        if(t[rt<<1])
            return findl(rt<<1,l,m);
        return findl(rt<<1|1,m+1,r);
    }
    int next(int p,int rt,intl,int r)
    {
        if(p<l)
        {
            if(t[rt])
                return findl(rt,l,r);
            return 0;
        }
        int m=(l+r)>>1;
        int re;
        if(p<m&&t[rt<<1]&&(re=next(p,rt<<1,l,m)))
            return re;
        return next(p,rt<<1|1,m+1,r);
    }
    

    第三:主席树
    好了,终于到了正题,我们要讲的主席树
    主席树据说是黄嘉泰大佬在比赛场地上,因为写题的需求,在赛场上自创的一种线段树运用。
    主席树
    1、以前缀和形式建立的可持久化线段树
    2、基于动态开结点的存储形式
    3、每次插入一个值时,最多新开O(log(n))个结点
    4、空间复杂度O(n*log(n))
    5、单次操作时间复杂度O(log(n))
    6、可以查询区间的值域信息
    7、相对于线段树套平衡树的优势:代码简单、速度快
    8、劣势:离线数据结构,难以修改。(可以采取对询问分块等方式弥补)
    可持久化思想:部分重建
    主席树的询问与权值线段树本质相同,只是要在区间作差

    主要思想:
    用主席树构造一颗可持久化权值线段树,对于每个数字,将其离散化后,新建一个版本的权值线段树,然后插入这个离散化后的数字。例如对于25957 6405 15770 26287 26465 离散化结果:3 1 2 4 5这五个数字的序列。我们就要依次建立五个版本的权值线段树,分别插入3 1 2 4 5这五个数。这就是“对原序列的每一个前缀建树”
    对于查询操作L,R,我们利用主席树的函数性质,用R那个版本的权值线段树减去L-1那个版本的权值线段树,在得到的权值线段树中查找第K小值就可以了。
    因为权值线段树存储的是值域上值的个数,我们用R版本的权值线段树减去L-1版本的权值线段树,得到的就是维护[L,R]上值的个数的权值线段树

    如何存储主席树:
    首先可以建立一个数组int root[manl],来储存各个根节点的编号。对于子结点,可以看出主席树不像线段树可以用当前节点编号乘2和乘2加1来得到左右儿子的节点编号。于是我们可以用struct存储当前节点的左右儿子节点编号。于是我们可以这样做:用一个struct开一个内存池,每新建一个主席树的结点,就从内存池里取一块新的空间送给这个结点,取空间从hjt[1]开始,hjt[0]充当NULL

    线段树是读完所有数据后再执行操作,而主席树是先读入一个,然后剩下的,一边插入,一边建树即可
    主席树一开始里面什么都没有,所以所有的节点l,r,sum都是0,而全局变量和数组都是默认赋值为0的。

    构造节点

    struct node
    {
    	int l;
    	int r;
    	int sum;
    };//l是左子树,r是右子树,sum是当前的权值
    struct node tree[maxl*4];
    

    对于主席树,我们一般采用节点来实现,在节点中存储其左子树,右子树和当前节点的权值的信息。
    离散化函数

    int getid(int x)
    {
    	return lower_bound(v.begin(),v.end())-v.begin()+1;
    }
    

    通过int getid()函数我们获得x在存储的值中的相对位置

    建树和对树的更新

    void update_tree(int l,int r,int &x,int y,int pos)
    {
    	tree[++cnt]=tree[y];
    	tree[cnt].sum++;
    	x=cnt;
    	if(l==r);
    		return;
    	int mid=(l+r)>>1;
    	if(mid>=pos)
    		update_tree(1,mid,tree[x].l,tree[y].l,pos);
    	else
    		update_tree(mid+1,r,tree[x].r,tree[y].r,pos);
    }
    

    主席树的建树和更新是一起的,每当输入一个值的时候,就会依托于最近的一颗主席树来进行新的一次构建。
    cnt为内存池。

    遍历

    int query(int l,int r,int x,int y,int k)
    {
    	if(l==r)
    		return l;
    	int mid=(l+r)>>1;
    	int sum=tree[tree[y].l].sum-tree[tree[x].l].sum;
    	if(sum>=k)
    		return query(l,mid,tree[x].l,tree[y].l,k);
    	else
    		return query(mid+1,r,tree[x].r,tree[y].r,k-sum);
    }
    

    完整代码来惹

    /*
    题意:
    7 3
    1 5 2 6 3 7 4
    2 5 3
    4 4 1
    1 7 3
    7个数字 3次询问, 7个数字分别是 1 5 2 6 3 7 4
    三次询问分别:
    从第二个到第五个数字中间 排第三个多的数字是
    */
    /*
    input
    7 3
    1 5 2 6 3 7 4
    2 5 3
    4 4 1
    1 7 3
    output
    5
    6
    3
    */
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    using namespace std;
    const int maxl=1e5+6;
    int n,m,cnt,root[maxl],a[maxl],x,y,k;
    //a数组用来存放数字
    //root数组用来建树
    struct node
    {
        int l;
        int r;
        int sum;
        //l是左子树,r是右子树,sum是当前的权值
    };
    struct node tree[maxl*4];
    vector<int>v;
    int getid(int x)//得到位置,离散化的第二步
    {
        return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    }
    void update(int l,int r,int &x,int y,int pos)
    {
        //每建立一个新的结点,都需要以前一个结点,建立当前结点
        tree[++cnt]=tree[y];
        tree[cnt].sum++;//由于新插入一个数 所以权值增加
        x=cnt;
        if(l==r)
            return;
        int mid=(l+r)/2;
        if(mid>=pos)
            update(l,mid,tree[x].l,tree[y].l,pos);
            //若插入在左边就用前一个的左子树为依托建立当前要建立的左子树
        else
            update(mid+1,r,tree[x].r,tree[y].r,pos);
            //若插入在右边就以前一个的右子树为依托建立当前右子树
    }
    int query(int l,int r,int x,int y,int k)
    {
        // x是原来的y是现在的
        //从l到r维护当前节点的区间
        if(l==r)
            return l;
        int mid=(l+r)/2;
        int sum=tree[tree[y].l].sum-tree[tree[x].l].sum;
        if(sum>=k)
            return query(l,mid,tree[x].l,tree[y].l,k);
        else
            return query(mid+1,r,tree[x].r,tree[y].r,k-sum);
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());//通过离散化后,已经排好的数组,如题:v即为1,2,3,4,5,6,7
        for(int i=1;i<=7;i++)
            cout<<a[i]<<"   "<<getid(a[i])<<endl;
        for(int i=1;i<=n;i++)
        {
            update(1,n,root[i],root[i-1],getid(a[i]));//对每一个输入数字进行建树
        }
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y>>k;
            cout<<v[query(1,n,root[x-1],root[y],k)-1]<<endl;
        }
        return 0;
    }
    
    
    展开全文
  • 为啥叫主席? 很多人一看到这名字觉得这肯定是个很厉害的数据结构,从而望而却步。 其实为啥这个数据结构叫主席呢,emmmm… 这个数据结构是这位同学在考场上想出来的,而他的名字与某位主席缩写有一致的相似性...

    为啥叫主席树?

    很多人一看到这名字觉得这肯定是个很厉害的数据结构,从而望而却步。
    其实为啥这个数据结构叫主席树呢,emmmm…
    在这里插入图片描述
    这个数据结构是这位同学在考场上想出来的,而他的名字与某位主席缩写有一致的相似性QAQ


    引入题(静态区间第k小)

    题目描述

    如题,给定 n n n 个整数构成的序列,将对于指定的闭区间查询其区间内的第 k k k 小值。

    输入格式

    第一行包含两个正整数 n , m n,m n,m,分别表示序列的长度和查询的个数。

    第二行包含 n n n 个整数,表示这个序列各项的数字。

    接下来 m m m 行每行包含三个整数 l , r , k l, r, k l,r,k , 表示查询区间 [ l , r ] [l, r] [l,r] 内的第 k k k 小值。

    输出格式

    输出包含 k k k 行,每行一个整数,依次表示每一次查询的结果

    输入输出样例
    输入 #1

    5 5
    25957 6405 15770 26287 26465
    2 2 1
    3 4 1
    4 5 1
    1 2 2
    4 4 1

    输出 #1

    6405
    15770
    26287
    25957
    26287


    想想怎么解决这题

    唔好像只会暴力

    如果简化一下

    先假设每个数值域都在 [ 1 , n ] [1,n] [1,n]
    假如每次询问都是问 [ 1 , n ] [1,n] [1,n] 的第 k k k 大,那怎么做呢?(雾似乎直接排序然后输出就好了
    但如果我们硬要用数据结构来动态查询呢?我们学过啥?
    权值线段树!!!
    权值线段树的每个叶子节点代表的是一个数,节点的值是这个数出现的次数。
    那么我们每次查找 [ 1 , n ] [1,n] [1,n] 中的第 k k k 大,查询的时候判断一下 k k k s u m [ l s o n ] sum[lson] sum[lson] 的大小,如果 k k k 小,说明 [ l , m ] [l,m] [l,m] 范围内已经有了不止 k k k 个数,说明第 k k k 大肯定在左子树内,于是就往左子树查询第 k k k 大数,否则就往右子树查询第 k − s u m [ l s o n ] k - sum[lson] ksum[lson] 大的数。

    问题来了

    现在求的不是区间 [ 1 , n ] [1,n] [1,n],而是区间 [ l , r ] [l,r] [l,r],这怎么破呢?
    要是我们能够在 [ l , r ] [l,r] [l,r] 之间建一棵权值线段树就好了QAQ
    没错这就是主席树的思想!
    为了得到区间 [ l , r ] [l,r] [l,r] 的权值线段树!
    如果我们得到了 [ 1 , r ] [1,r] [1,r] [ 1 , l − 1 ] [1,l-1] [1,l1] 的权值线段树,那么求 [ l , r ] [l,r] [l,r] 每个节点的 s u m sum sum 值不就是 s u m [ r t ] − s u m [ l a s ] sum[rt] - sum[las] sum[rt]sum[las] 了吗!!!
    r t rt rt [ 1 , r ] [1,r] [1,r] 的权值线段树的当前节点, l a s las las [ 1 , l − 1 ] [1,l-1] [1,l1] 的权值线段树的当前节点


    进入正题(敲黑板

    考虑建立 [ 1 , i ] [1,i] [1,i] 的权值线段树

    如果我们每次都直接建树,时空复杂度还是爆炸
    问题在于我们每次都要重新建立 [ 1 , i − 1 ] [1,i-1] [1,i1] 的信息
    如果这部分信息能直接利用起来就好了!
    事实上真的可以直接用!!
    接着往下看!

    建树

    在这里插入图片描述
    这个图是 [ 1 , i ] [1,i] [1,i] 的权值线段树,可以看到,每颗权值线段树,都和前一棵有很强的相似性!!!其实,每一棵和前一棵的区别仅仅在于一条链上!
    每次对 [ 1 , i ] [1,i] [1,i] 建树,插入 a [ i ] a[i] a[i] 这个节点时,最多只会影响到 l o g n logn logn 个节点的 s u m sum sum 值 (单点插入的复杂度是 l o g n logn logn),我们其实只要建这 l o g n logn logn 个节点就好了!其他节点直接用 i − 1 i-1 i1 那棵树的,就可以避免重复建树!
    先看看 u p d a t e update update 部分的代码

    void update(int l, int r, int &rt, int p, int las){
    	rt = ++cnt;
    	sum[rt] = sum[las] + 1;
    	lch[rt] = lch[las];
    	rch[rt] = rch[las];
    	if(l == r) return;
    	int m = l + r >> 1;
    	if(p <= m) update(lson, p, lch[las]);
    	else update(rson, p, rch[las]);
    }
    

    这里我们用的是动态开点,也就是对于每一个和前一棵树不同的点,都对它单独开一个新的空间。
    很容易发现,我们每次 u p d a t e update update,都会开 l o g n logn logn 个空间,所以主席树的空间复杂度是 n l o g n nlogn nlogn

    查询

    查询部分的原理就是权值线段树!上面已经说过了!
    直接看代码!

    int find(int l, int r, int rt, int k, int las){
    	if(l == r) return l;
    	int s = sum[lch[rt]] - sum[lch[las]], m = l + r >> 1;
    	if(k <= s) return find(lson, k, lch[las]);
    	return find(rson, k - s, rch[las]);
    }
    

    s u m [ r t ] − s u m [ l a s ] sum[rt] - sum[las] sum[rt]sum[las] 就是 [ l , r ] [l,r] [l,r] 的权值线段树的节点的 s u m sum sum 值!
    如果你理解了上面的部分,这里应该很好理解!

    最后补充一下主席树一般用到的一些东西

    离散化

    在一般的题目中,数据范围一般不是 [ 1 , n ] [1,n] [1,n],而是 i n t int int 范围,于是我们要离散化,把数据映射到 [ 1 , n ] [1,n] [1,n] 范围。其实离散化就是用每个数的排名来代替这个数,要访问这个数只要在原来排序后的数组中访问下标就可以了。
    也就是说,离散化后,我们用这个数的排名来代替这个数了!

    离散化代码如下

    	for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    	sort(b + 1, b + i);
    	m = unique(b + 1, b + n + 1) - b - 1;
    	for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    

    u n i q u e unique unique 的作用是去重, m m m 是去重后的数组有多少个数。

    总代码如下

    #include <bits/stdc++.h>
    #define N 200005
    #define lson l, m, lch[rt]
    #define rson m + 1, r, rch[rt]
    using namespace std;
    int cnt, root[N], lch[N * 32], rch[N * 32], sum[N * 32], a[N], b[N];
    void build(int l, int r, int &rt){
    	rt = ++cnt;
    	if(l == r) return;
    	int m = l + r >> 1;
    	build(lson);
    	build(rson);
    }
    void update(int l, int r, int &rt, int p, int las){
    	rt = ++cnt;
    	sum[rt] = sum[las] + 1;
    	lch[rt] = lch[las];
    	rch[rt] = rch[las];
    	if(l == r) return;
    	int m = l + r >> 1;
    	if(p <= m) update(lson, p, lch[las]);
    	else update(rson, p, rch[las]);
    }
    int find(int l, int r, int rt, int k, int las){
    	if(l == r) return l;
    	int s = sum[lch[rt]] - sum[lch[las]], m = l + r >> 1;
    	if(k <= s) return find(lson, k, lch[las]);
    	return find(rson, k - s, rch[las]);
    }
    int main(){
    	int i, j, n, m, l, r, k, T, q;
    	//scanf("%d", &T);
    	T = 1;
    	while(T--){
    		scanf("%d%d", &n, &q);
    		memset(root, 0, sizeof(root));
    		memset(lch, 0, sizeof(lch));
    		memset(rch, 0, sizeof(rch));
    		memset(sum, 0, sizeof(sum));
    		cnt = 0;
    		for(i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    		sort(b + 1, b + i);
    		m = unique(b + 1, b + n + 1) - b - 1;
    		for(i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    		build(1, m, root[0]);
    		for(i = 1; i <= n; i++) update(1, m, root[i], a[i], root[i - 1]);
    		for(i = 1; i <= q; i++){
    			scanf("%d%d%d", &l, &r, &k);
    			j = find(1, m, root[r], k, root[l - 1]);
    			printf("%d\n", b[j]);
    		}
    	}
    	return 0;
    }
    

    总结

    主席树其实就是区间的权值线段树。
    任何权值线段树能支持的查询操作主席树都能有
    主席树时空复杂度都是 O ( n l o g n ) O(nlogn) O(nlogn)

    完结撒花!!!

    展开全文
  • 1.引言 ...事实上,在这种树套树中,内层的每一颗线段树是独立的,并不是类似于可持久化线段树(广泛被接受的"主席树")那样的"互相依存"的线段树.但是由于"主席树"在\(OI\)界定义并不明确,有些语境下也可...
  • 思路:权值线段树模板 #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<bits/stdc++.h> ...
  • 权值线段树找第k大

    2019-08-19 22:16:13
    1 k,输出一个数表示答案 示例1 输入 复制 5 3 1 2 3 4 5 1 3 2 1 5 1 3 输出 复制 3 4 思路 权值线段树,利用底层节点区间编号L表示a[i]的值,节点的权值表示对应值的个数。父亲节点权值为两个儿子节点权值之和,...
  • 权值线段树学习(模板+例题)

    千次阅读 2019-04-10 20:20:01
    之前写一道题的时候,看到了一个数据结构叫做权值线段树,跟普通的线段树不太一样,一直没有仔细看,上课无聊,随手推了推,画了几张图,感觉容易多了。 权值线段树 普通线段树基本上会点数据结构的人都知道了,...
  • 权值线段树,顾名思义,是一数的值的大小作为下标建立数段树的,所以通常需要先离散化再建树。个人感觉有点像主席树,只是不是可持久化的而已。 作用(个人观点):查询某个数的排名,有多少个数比它小,比它大,...
  • 权值线段树写,注意要先离散化 (3)求x的排名,就是求[1,x-1]的区间sum值+1 (5)求x的前驱,就是sum(1,x-1)求出1到x-1的所有数的个数,再求排名为sum(1,x-1)的数 (6)求x的后继,就是sum(1,x)求出1到x...
  • 线段树大概地球人都知道了,就是以数组的下表建立线段树来进行一些区间操作,这里介绍一下权值线段树,顾名思义,其实权值线段树也是线段树的一种。 一:权值线段树线段树与简单线段树的区别就像他的名字一样,他...
  • 权值线段树 HDU1396 Minimum Inversion Number 求序列最小逆序数 权值线段树单点更新区间查询 #include&lt;bits/stdc++.h&gt; using namespace std; const int MAX=5e3+5; int a[MAX],n; struct P { ...
  • 普通线段树中我们在每个节点存储的是某段区间的一些信息,而权值线段树,我们存的是值为该下标的数的个数,并通过线段树统计某段区间的信息。 它能干嘛? 最最简单的用途就是动态统计在某个取值范围内的数的个数嘛,...
  • 前言:所谓权值线段树,其实是很简单的一个数据结构,它通常用log n的询问来求第k大,第k小这样的问题,它自身的实现也是非常简单。 首先我们得了解权值线段树所维护的东西。权值线段数,它每一个区间所代表的,是...
  • 权值线段树总结

    2019-08-14 20:40:00
    权值线段树就是把线段树的每个点权,赋予一定的含义,比如数字出现的次数,数值前缀出现的次数,并用区间求和维护一个前缀信息,比如数字出现的次数,第K大等(不能实现区间第K大),前缀第K大等。 权值线段树优点...
  • 权值线段树就是在线段树的基础上,将每一个点作为一个桶。区间l到r表示从[l…r]这个数值之间的信息。每个节点维护一个数值的数量,表示[l…r]这个区间有多少个数。 支持的操作: 添加一个元素 查找一个元素出现的...
  • 动态开点线段树+权值线段树概述

    千次阅读 2018-03-28 16:15:56
    所以动态开点和权值线段树基本上是在一起的,所以笔者就放在一起讲啦!!!再来安利一道题: P2471 [SCOI2007]降雨量 。这道如果你不想离散化的话,可以写写动态开点线段树。注意!!!心脏不好的请不要写这道题。
  • 首先先上一个主席求区间第K小的板子 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mid (l+r)/2 using namespace std; const int N = 1e6+4; int ...
  • 树状数组套权值线段树 #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn=2e6+5; int rt[maxn*2],ls[maxn*20],rs[...
  • 权值线段树 学习笔记

    2020-03-06 20:41:58
    权值线段树 权值线段树是基于线段树的一种数据结构; 线段树维护的是区间信息,比如区间和,区间最大值等等; 而权值线段树维护的是全局的值域信息,每个结点记录是该结点所包含区间的值出现的次数; 权值线段树支持...
  • 分类简述 一般的trie 并没有什么特别的,可以O(n)进行字符串...权值线段树 二进制trie 注意: - 充分理解在高层结点决策的思想,因为边才是权值。 - 直接一位对一位,调位置太麻烦了。 - 注意那个bool运算...
  • 很不错的一道思维题。 Code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include&lt;iostream&gt; using namespace std; const int maxn = 1000000 + 4;...int root[maxn], m...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,015
精华内容 7,206
关键字:

权值线段树