您现在的位置是:首页 > 正文

HDU2665 主席树原理解决静态区间第K大值问题总结 有详细图解和代码解释

2023-12-01 05:00:35阅读 6

鄙人不才,刚学习了一点主席树,想自己来写一篇关于主席树的详解,主要针对主席树解决静态(无修改)区间内第K大值的问题,可以参考HDU 2665。解决其他的问题的主席树算法等自己搞懂后再补上。下文如果有什么错误还请指出,感激不尽!


感谢以下博文对主席树的讲解:

1.主席树1

2.主席树2

3.主席树3

 

前置技能

1.线段树。

2.前缀和。

3.sort函数、unique函数以及lower_bound函数的使用方法。

 

主席树又叫函数式线段树,其实就是多颗线段树的相互连接形成的一种数据结构。主席树这个名字和它的功能毛关系都没有,如果你乐意,叫它狗蛋树都可以。其时间复杂度和空间复杂度都为为 O(nlogn).

 

言归正传,首先来看一下求静态区间第K大值的问题。平常的做法是先将该区间排序,然后求出第K大值,一旦求多组区间第K大值的话,时间复杂度就很高了。这时候就得用到主席树。

 

我们先来简化一下问题:求整个区间的第K大值问题。我们可以用线段树解决,让线段树的第 i 个叶子节点表示原数组中排第 i 的有多少个,而其他节点表示排第L~R 的有多少个,其中L、R 就是它控制的范围[L,R] 。例如,给你一组数:1,2,2,2,4,4,8. 让你求第5 小的数,你发现排第 1~4 小的数分别有 1,3,2,1 个,很明显排第5小的数在前面红色的数字 2 表示的数中,也就是数字4。


现在再来考虑求任意区间的第K大值。这里利用到了前缀和的知识,比如给你一组数让你求区间[L,R] 内的和,一个简单的方法就是求出前缀和 sum[i]=a[1]+a[2]+…+a[i] ,然后让sum[R]-sum[L-1] 就是结果。这里也是一样,假设有 n 个数,我们需要建立n 颗结构完全相同(即节点个数和位置等都相同,只是节点表示的值不同)的线段树,也就是对原数组的每前 i 个值都建立一颗类似于前缀和的线段树,我们让第i 颗线段树存储区间 [1, i ] 内的第 1~K 大值情况,其中K为原数组中不同数的个数。根据上一段落中的介绍,我们是可以实现的。如果要计算区间 [L,R] 的第K大值,只需要让第R颗线段树的节点减去第L-1颗线段树对应的节点,然后在新的线段树上查找即可。

为什么这样是可行的呢?前面说过了因为所有的线段树都是同构的,每个节点代表的意思相同,都是前 i 个数中排在第 L~R 的数的个数。第 i 和第 j-1 颗线段树一相减就表示在第 j-1 ~ i 个数中排在第 L~R 的数的个数。这样说起来可能有点绕,下面让我们看下图。

 

一、建树

下面的图针对的是数据:1,4,2,3所建的树。


 

上图是初始化时的状况,这时候还没往树中插入任何元素。图中每个矩形块表示一个节点,其中间绿色的数字表示当前数形成的线段树中排第L~R 的数的个数,其中L、R是这个节点所能表示的范围 [L,R]。矩形的左右两端的数就是这个节点表示的范围L和R了。至于节点外的数字可以看作是节点的编号,从1开始,按照中根遍历的顺序编号。对于每个叶子节点下面的红色数字表示的是在原数组中排第几。第 i 个叶子节点自然是表示排第 i 了。

 


上图分别为插入第1个数和插入第2个数所形成的线段树。我们将上面两图的对应节点相减一下,是不是就得到了只插入第 2 个数时候形成的线段树呢?这里我想再强调一点,线段树的第 i 个叶子节点保存的不是数的值,而是在原数组中排第 i 的数有多少个,而其他节点表示的是排第 L~R 的数有多少个,其中L、R 就是这个节点所能表示的范围 [L,R]。

 

 

二、更新

上面说到了,如果原数组有n 个节点的话需要建立n 个线段树,用脚指头想都会觉得十分耗费空间。我们发现,第 i 个线段树是在第i-1 个线段树的基础上改变了一些值而来的。所以,我们可不可以共用那些没有改动的值呢?当然是可以的了。

 

 

如上图所示,插入第 1 个数形成的线段树和初始化时的线段树的改动的部分就是图中红线圈起来的部分。所以我们只需要在原线段树的基础上加上这些点即可,其他点共用即可。

 


如上图所示,红色的部分就是插入第 1 个数形成的线段树,它共用了前一个线段树的一部分。注意,这时候新节点的编号不是从1开始重新编号的。

 

 

又如上图所示,蓝色的部分就是插入第 2 个数形成的线段树,它又共用了前一个线段树的一部分。


正是通过考虑到插入一个数的时候只会更改log(n) 个节点,也就是树高个节点,所以这需要添加这些节点即可,这样一来就实现了压缩空间的目的。

 

 

三、查询

就如上面提到过的,如果要查询区间 [L,R] 先要让第R 颗线段树减去第L 颗线段树,然后在得到的新树中查找,其实这个过程可以一边相减一边查找,因为你要查找一个第K 大数,它所查找经过的节点路径是一定的。例如你要查找第K 大数,已经得到了相减后的新树,如果新树根节点的左子树中有num 个数,如果num>=k ,则说明要查找的数在左子树中,否则在右子树中,利用递归查找即可,当区间长度为 1 时就查找到了。

 

 

具体实现:

我们用L、R数组保存节点所能表示的范围 [L,R],sum数组表示排第第L~R 的数的个数。tol表示节点的编号,如果编号相同,则L、R、sum表示同一个节点。当然这里也可以用一个结构体保存一下。

a数组保存原数组,hash数组保存排序后的数组,T数组保存插入每个元素后形成的线段树的根节点的编号

如果原数组中有n 个不同的数,则我们建一个叶子节点有n 个的线段树就可以了。它们分别排第 1~n 。获取不同的数的个数可以用unique函数。查找当前数排第几可以用lower_bound函数。


总结一下:主席树就是对原数组的前 i 个数建一颗线段树保存前 i 个数的第 1~n 大值信息,其中 n 为原数组中不同数的个数。由于插入当前数时只改变了logn个节点的值,所以前一棵树可以重复利用,大大节省了空间。在查询时,利用前缀和的性质,区间 [L,R] 对应的第 R颗数减去第 L-1 棵树,得到这段区间内的第 1~n 大值信息,然后查找。如果左子树中的数的个数大于要查找的 K ,则结果在左子树中,否则在右子树中查找。


下面是HDU 2665的AC代码,如果注释有什么不正确的地方还请大家多多指正~

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;

int tol;
//若tol值相同,则L、R、sum就表示同一个节点
//L为左端点的编号,R为右端点的编号,sum表示区间[L,R]内数的个数 
int L[MAXN<<5],R[MAXN<<5],sum[MAXN<<5];
int a[MAXN],T[MAXN],Hash[MAXN]; //T记录每个元素对应的根节点 

//建树函数,建立一颗空树
int build(int l,int r)
{ //参数表示左右端点 
    int mid,root=++tol;
    sum[root]=0; //区间内数的个数为0
    if(l<r)
    {
        mid=(l+r)>>1;
        L[root]=build(l,mid);   //构造左子树并将左端点编号存入L 
        R[root]=build(mid+1,r); //构造右子树并将右端点编号存入R
    }
    return root;
}

//更新函数
int update(int pre,int l,int r,int pos)
{//参数分别为:上一线段树的根节点编号,左右端点,插入数在原数组中排第pos 
	//从根节点往下更新到叶子,新建立出一路更新的节点,这样就是一颗新树了。
    int mid,root=++tol;
    L[root]=L[pre]; //先让其等于前面一颗树 
    R[root]=R[pre]; //先让其等于前面一颗树
    sum[root]=sum[pre]+1; //当前节点一定被修改,数的个数+1 
    if(l<r)
    {
        mid=(l+r)>>1;
        if(pos<=mid) L[root]=update(L[pre],l,mid,pos); //插入到左子树 
        else R[root]=update(R[pre],mid+1,r,pos); //插入到右子树 
    }
    return root;
}

//查询函数,返回的是第k大的数在原数组中排第几
int query(int u,int v,int l,int r,int k)
{ //参数分别为:两颗线段树根节点的编号,左右端点,第k大 
    //只会查询到相关的节点 
    int mid,num;
    if(l>=r) return l;
    mid=(l+r)>>1;
    num=sum[L[v]]-sum[L[u]]; //当前询问的区间中左子树中的元素个数
    //如果左儿子中的个数大于k,则要查询的值在左子树中 
    if(num>=k) return query(L[u],L[v],l,mid,k); 
    //否则在右子树中 
    else return query(R[u],R[v],mid+1,r,k-num);
}

int main()
{
    int i,n,m,t,d,pos;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            Hash[i]=a[i];
        }
        sort(Hash+1,Hash+n+1);
        d=unique(Hash+1,Hash+n+1)-Hash-1; //d为不同数的个数
        tol=0; //编号初始化 
        T[0]=build(1,d); //1~d即区间 
        for(i=1;i<=n;i++)
        { //实际上是对每个元素建立了一颗线段树,保存其根节点
            pos=lower_bound(Hash+1,Hash+d+1,a[i])-Hash;
            //pos就是当前数在原数组中排第pos 
            T[i]=update(T[i-1],1,d,pos);
        }
        int l,r,k;
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&k);
            pos=query(T[l-1],T[r],1,d,k);
            printf("%d\n",Hash[pos]);
        }
    }
    return 0;
}

文章来源:https://blog.csdn.net/zuzhiang/article/details/78173412
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://www.dflian.com/184959.html

网站文章

  • Linux基础——Shell编程之条件语句

    Linux基础——Shell编程之条件语句

    测试表达式是否成立,若成立返回0(正常),否则返回其他数值(非零值都为异常)格式1:[ 表达式1 ] 操作符 [ 表达式2 ]…语法:[ 整数1 操作符 整数2 ]语法:[ 操作符 文件或目录 ]格式2:命令1 操作符 命令2…格式1: test 条件表达式。格式2: [ 条件表达式 ]

    2023-12-01 05:00:30
  • 前端H5页面在真机调试查看请求接口的插件

    前端H5页面在真机调试查看请求接口的插件

    安装:npm i vconsolenpm i vconsole然后在main.js文件添加代码:import Vconsole from 'vconsole';const VConsole = new Vconsole();// console.log(VConsole);然后运行页面就可以看到调试的小窗口了打开之后是这样的成功!...

    2023-12-01 05:00:26
  • 泛型类相关

    泛型类相关

    泛型类相关

    2023-12-01 05:00:20
  • pdfPCell中设置单元格 setRowspan()与setColspan(),setPadding(),setBorder()

    pdfPCell中设置单元格 setRowspan()与setColspan(),setPadding(),setBorder()

    打印pdf格式:打印的表格如下:

    2023-12-01 05:00:14
  • java报错--org.springframework.beans.factory.BeanCreationException

    java报错--org.springframework.beans.factory.BeanCreationException

    org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'bookControll...

    2023-12-01 04:00:28
  • 溢出原理《转》

    其实所谓溢出原理:即是数据存储过程中超过数据结构所能容纳的实际长度都可成为溢出。我认为要浅显读懂该文必须了解计算机语言,计算机数制相关知识。如果要深入研究溢出则必须深入学习计算机程序设计相关知识,比如计算机数据结构,计算机编译原理,微机接口与组成原理等等。这里取前者,浅显谈谈计算机语言,计算机数制相关知识。一。浅谈计算机语言众所周知,计算机是0,1的二进制数字世界,所谓电子计算机乃是用电的低电平表

    2023-12-01 04:00:24
  • 局部性原理

    局部性原理

    cpu cache结构 内存&gt;L3&gt;L2&gt;L1多级缓存 这四级的速度是越来越快 本质上内存是一个大的一维数组二维数组在内存中按照行排列,先放a【0】再放a【1】 第一种arr1的遍历...

    2023-12-01 04:00:21
  • ForkJoin看这篇就够了!

    求解出子问题的解,合并得到原问题的解。Fork/Join采用的是分而治之的基本思想,分而治之就是将一个复杂的任务,按照规定的阈值划分成多个简单的小任务,然后将这些小任务的结果再进行汇总返回,得到最终的...

    2023-12-01 04:00:16
  • js轮询导致服务器瘫痪_websocket连接太多导致服务器卡顿怎么办?一招轻松实现横向扩展...

    前言项目中有即时聊天的需求,经过调研我们采用了socket.io自己实现了一个聊天服务器。开始的一段时间由于用户不是很多,消息的发送接收都还算流畅,最近随着在线用户数量飙升,每过一段时间就会发生发送消...

    2023-12-01 04:00:13
  • TCP第四次挥手为什么要等待2MSL(最长报文段寿命,Maximum Segment Lifetime)

    TCP第四次挥手为什么要等待2MSL(最长报文段寿命,Maximum Segment Lifetime)

    当客户端进入TIME-WAIT状态的时候(也就是第四次挥手的时候),必须经过时间计数器设置的时间2MSL(最长报文段寿命)后,才能进入关闭状态,这时为什么呢??? 这最主要是因为两个理由: 1、为了保...

    2023-12-01 03:00:40