`
hellojyj
  • 浏览: 61454 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

线段树模板

 
阅读更多
int Max[MAXN];      //子区间中的最大值
int ql,qr,p,v;
//ql:查询左边界,qr:查询右边界,p:更新点 v:更新值

//建立线段树
void build(int r,int L,int R)
{
    //如果到了叶节点(区间长度为1),最大值当然是叶节点值;
    if(L==R) scanf("%d",Max+r);
    else
    {
        int M = (L+R)/2;        
        build(r*2,L,M);         //递归建立左子树
        build(r*2+1,M+1,R);    //递归建立右子树
        Max[r] = max(Max[r*2],Max[r*2+1]);  //将左右子区间的最大值更新到根节点
        
    }
}
//对线段树进行查询操作
int query(int r,int L,int R)
{
    int ans = -1;
    int M = (L+R)/2;
    
    //如果该区间在所在查询区间内,那么返回改区间节点的最大值
    if(ql<=L&&R<=qr)
        return Max[r];
    //如果右边界小于中间值,那么所要查询区间一定在左子区间
    if(qr<=M)
        return query(r*2,L,M);
    //如果左边界大于中间值,那么所要查询区间一定在右子区间
    else if(ql>M)
        return query(r*2+1,M+1,R);
    //除了以上两种情况可能的是左边界和右边界跨越两个子区间
    //那么返回两个子区间的最大值
    else
        ans = max(query(r*2,L,M),query(r*2+1,M+1,R));
    return ans;
}
//更新线段树
void update(int r,int L,int R)
{
   int M = (L+R)/2;
   
   //查到更新点,更新值
   if(L==R) Max[r] = v;
   else
   {
       //如果更新点小于中间值,递归更新左子区间
       if(p<=M)
        update(r*2,L,M);
        
        //否则递归更新右子区间
       else
        udapte(r*2+1,M+1,R);
        
        //更新根节点
       Max[r] = max(Max[r*2],Max[r*2+1]);
   }
}

 

分享到:
评论

相关推荐

    基于微信小程序的在线办公小程序答辩PPT.pptx

    基于微信小程序的在线办公小程序答辩PPT.pptx

    机器学习(预测模型):2000年至2015年期间193个国家的预期寿命和相关健康因素的数据

    这个数据集来自世界卫生组织(WHO),包含了2000年至2015年期间193个国家的预期寿命和相关健康因素的数据。它提供了一个全面的视角,用于分析影响全球人口预期寿命的多种因素。数据集涵盖了从婴儿死亡率、GDP、BMI到免疫接种覆盖率等多个维度,为研究者提供了丰富的信息来探索和预测预期寿命。 该数据集的特点在于其跨国家的比较性,使得研究者能够识别出不同国家之间预期寿命的差异,并分析这些差异背后的原因。数据集包含22个特征列和2938行数据,涉及的变量被分为几个大类:免疫相关因素、死亡因素、经济因素和社会因素。这些数据不仅有助于了解全球健康趋势,还可以辅助制定公共卫生政策和社会福利计划。 数据集的处理包括对缺失值的处理、数据类型转换以及去重等步骤,以确保数据的准确性和可靠性。研究者可以使用这个数据集来探索如教育、健康习惯、生活方式等因素如何影响人们的寿命,以及不同国家的经济发展水平如何与预期寿命相关联。此外,数据集还可以用于预测模型的构建,通过回归分析等统计方法来预测预期寿命。 总的来说,这个数据集是研究全球健康和预期寿命变化的宝贵资源,它不仅提供了历史数据,还为未来的研究和政策制

    基于微信小程序的“健康早知道”微信小程序答辩PPT.pptx

    基于微信小程序的“健康早知道”微信小程序答辩PPT.pptx

    基于微信小程序的电影交流平台答辩PPT.pptx

    基于微信小程序的电影交流平台答辩PPT.pptx

    计算机字符编码GB18030.PDF

    计算机字符编码GB18030

    Hive 操作基础(进阶版)多级分区数据文件2

    Hive 操作基础(进阶版)多级分区数据文件2

    基于java的贫困生管理系统答辩PPT.pptx

    基于java的贫困生管理系统答辩PPT.pptx

    pandas-2.1.4-cp312-cp312-win_amd64.zip

    pandas whl安装包,对应各个python版本和系统(具体看资源名字),找准自己对应的下载即可! 下载后解压出来是已.whl为后缀的安装包,进入终端,直接pip install pandas-xxx.whl即可,非常方便。 再也不用担心pip联网下载网络超时,各种安装不成功的问题。

    TA_Lib轮子无需编译-TA_Lib-0.4.18-cp38-cp38-win32.whl.zip

    TA_lib库(whl轮子),直接pip install安装即可,下载即用,非常方便,各个python版本对应的都有。 使用方法: 1、下载下来解压; 2、确保有python环境,命令行进入终端,cd到whl存放的目录,直接输入pip install TA_lib-xxxx.whl就可以安装,等待安装成功,即可使用! 优点:无需C++环境编译,下载即用,方便

    课设毕设基于SpringBoot+Vue的瑜伽体验课预约系统源码可运行.zip

    本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac

    tornado-6.2b2.tar.gz

    tornado-6.2b2.tar.gz

    javawe论坛项目 原生技术

    javawe论坛项目 原生技术

    tornado-6.2b1-cp310-cp310-macosx_10_9_universal2.whl

    tornado-6.2b1-cp310-cp310-macosx_10_9_universal2.whl

    基于司机信用评价的货运管理系统(springboot+vue+mysql+说明文档).zip

    随着物流行业的快速发展,货运管理变得愈发重要。为了提高货运效率,确保货物安全,我们开发了这款基于司机信用评价的货运管理系统。 该系统主要包含了货物信息管理、订单评价管理、货主管理等多个功能模块。在货物信息管理模块中,用户可以查看和管理货物的详细信息,包括货物名称、规格、装车状态、运输状态以及卸货状态等,方便用户随时掌握货物的动态。 订单评价管理模块是该系统的核心之一,它允许货主对司机的服务进行评价,系统会根据评价数据对司机进行信用评分。这一功能不仅有助于提升司机的服务质量,还能为货主提供更加可靠的货运选择。 此外,货主管理模块提供了货主信息的录入、修改和查询等功能,方便用户管理自己的货主资料。系统界面简洁明了,以蓝色为主色调,设计现代且专业,为用户提供了良好的使用体验。 通过该系统,用户可以轻松实现货物信息的查看和管理,对司机的服务进行评价,提高货运效率和服务质量。同时,系统也为司机提供了一个展示自我、提升信用的平台,有助于推动物流行业的健康发展。

    毕业生交流学习平台 SSM毕业设计 附带论文.zip

    毕业生交流学习平台 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B

    基于java的广场舞团答辩PPT.pptx

    基于java的广场舞团答辩PPT.pptx

    基于java的基于SSM的校园音乐平台答辩PPT.pptx

    基于java的基于SSM的校园音乐平台答辩PPT.pptx

    安装包JIRATimeSLA

    Jira插件安装包

    【java毕业设计】基于图像识别与分类的中国蛇类识别系统源码(springboot+vue+mysql+说明文档).zip

    项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse

    tornado-6.2b2-cp37-abi3-win_amd64.whl

    tornado-6.2b2-cp37-abi3-win_amd64.whl

Global site tag (gtag.js) - Google Analytics