`
hellojyj
  • 浏览: 61717 次
  • 性别: 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]);
   }
}

 

分享到:
评论

相关推荐

    线段树模板__模板

    线段树模板 线段树是一种重要的数据结构,广泛应用于算法竞赛和实际问题中。下面我们将详细介绍线段树的定义、性质、时间复杂度和应用。 线段树的定义 线段树是一种二叉树,每个结点对应一个线段[a, b]。线段树...

    ZKW线段树模板类

    在ZKW_Segment_Tree.cpp和ZKW_Segment_Tree.h两个文件中,我们可以找到线段树模板类的实现。cpp文件通常包含了函数的具体实现,而h文件则定义了类的接口。类的构造函数可能接收一个整型数组,用于初始化线段树,而...

    线段树模板 zoj1128

    本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。

    自己写的线段树的模板_

    c++的线段树模板

    pascal区间线段树

    **Pascal 区间线段树详解** 线段树(Segment Tree)是一种数据结构,用于高效地处理数组或序列上的区间查询与修改操作。在Pascal编程语言中,我们可以使用记录(Record)类型来实现一个区间线段树。以下是基于给定...

    加法线段树模板.cpp

    加法线段树模板

    带懒惰标记的线段树模板

    带懒惰标记的线段树模板

    完整的线段树模板,基础模板

    本资源提供了一个完整的线段树基础模板,旨在帮助开发者快速掌握并应用线段树解决实际问题。 特点: 基础性:适合初学者和有一定基础的开发者,从零开始理解线段树的构建和运作原理。 完整性:包含了线段树的构建...

    线段树乘法模板(从基础线段树扩展)

    以下是针对标题为“完整的线段树模板,基础模板”的资源描述,但特别强调了线段树乘法的应用: 资源标题:完整的线段树模板,基础模板(含乘法操作) 资源描述: 线段树(Segment Tree)是一种强大的数据结构,...

    C++ 线段树模板(求和),100%正确性

    C++ 线段树模板(求和),100%正确性,希望可以多多支持,本博客还有题解等内容,欢迎观看,给予评价,若有建议可以私信!!!

    线段树(模板+例题——郭神)

    ### 线段树(Segment Tree):概念与应用 #### 一、线段树的基本概念 线段树,有时也被称为区间树,是一种高效的数据结构,主要用于处理区间查询和区间更新的问题。它通过将一个大的区间划分为若干个较小的、互不...

    基于Python的线段树实现与优化.pdf

    线段树是一种高效的数据结构,特别适用于区间修改、查询和维护的场景。在区间值的维护方面,线段树表现出了很高的效率,属于一种以空间换取时间的算法数据结构。它通过预处理区间和值来减少查询时的计算量,通常在...

    第3章 线段树 测试数据.rar

    线段树是一种高效的数据结构,常用于处理区间查询与更新问题。在信息学奥赛中,线段树是解决动态范围查询和修改的关键工具。本章的测试数据旨在帮助参赛者深入理解和熟练运用线段树。 线段树的核心思想是对一个数组...

    线段树数据结构

    线段树模板,采用二叉结构储存数据。适用于区间及点的修改与查询操做。是一种灵活性较大的数据结构。

    线段树入门学习(二)(兼解POJ3468) JAVA

    线段树是一种高效的数据结构,常用于解决区间查询与修改的问题。在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治...

    ZKW线段树源码-pascal

    ZKW线段树是一种高效的数据结构,用于处理连续或离散区间上的查询和更新操作。它属于高级编程技巧,在算法竞赛和编程实践中有着广泛的应用。Pascal语言实现的ZKW线段树源码,可以保证在对数时间复杂度logN内完成区间...

    线段树模版(比较基本的线段树以及例题模板)

    关于一些典型的线段树的例题,大家可以看一看,给一个评价,这些内容,后续我也会在博客上慢慢更新。希望大家多多的支持作者,谢谢! 这篇内容主要包含了一些我写的线段树的代码,可以帮助大家更好的理解线段树建树...

    线段树动态问题

    如何解决动态范围求和问题,如何简单地了解线段树。 附有模板以及习题

Global site tag (gtag.js) - Google Analytics