RMQ&线段树复习
需要包含必要的头文件，包括标准输入、字符串操作和算法库。 定义数据结构dmax和dmin分别用于存储区间内最大值和最小值。 实现了一个用于初始化最大值的预处理函数initmax。该函数采用动态规划的方式，计算不同区间的最大值。 实现了一个查询最大值的函数getmax，根据查询区间长度k快速定位预处理表中存储的最大值。 线段树需要维护数据的信息，常用于支持多个操作，如单点更新和区间查询。 线段树的节点包含左孩子和右孩子，用于划分查询区间。 建立线段树时，通过递归的方式将原始区间分解为叶子节点，再逐步合并节点值。 在查询操作中，根据查询范围，递归访问相关节点，累加结果。
发布日期：2021-05-14 13:34:45
浏览次数：11
分类：精选文章
本文共 500 字，大约阅读时间需要 1 分钟。
今天主要复习了RMQ和线段树，整理了一下模版。内容如下：
RMQ (范围最大值查询)
RMQ的核心思想是利用凑平方的方法离线处理查询。首先，我整理了与RMQ相关的预处理代码模版。
预处理部分：
线段树
在学习过程中，我也进一步复习了线段树的相关知识。以下是线段树单点更新和区间查询的模版：
线段树的关键点：
未来计划：
- 继续深入学习这两种数据结构，熟练掌握它们的解题思路和实现技巧。
- 应用到实际问题中，锻炼解题能力和创新思维。
发表评论
最新留言
很好
[***.229.124.182]2025年04月16日 18时06分40秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
算法训练——字符串合并
2019-03-09
信息学奥赛一本通【题目索引 + 解答】
2019-03-09
什么时候需要重写HashCode（）
2019-03-09
2021-04-23
2019-03-09
Linux编程基础之创建两个子进程而不创建孙子进程
2019-03-09
hadoop 分布式文件系统的计算和高可用
2019-03-09
【Linux】VMware Workstation 不可恢复错误: (vcpu-0)
2019-03-09
VS中 fatal error LNK1123: 转换到 COFF 期间失败 的解决方法
2019-03-09
关于Img标签在固定宽高的容器内部以图片比例缩放存在
2019-03-09
pyhton---异常处理的终极语法、网页访问基本读取、网页访问异常处理
2019-03-09
linux下编程出现 对'sem_wait'未定义的引用解决方案
2019-03-09
ant design pro v5去掉右边content区域的水印
2019-03-09
web_求和（练习）
2019-03-09
JavaScript——使用iterator遍历迭代map，set集合元素
2019-03-09
IAR调试卡顿的解决办法
2019-03-10
应用程序无法启动,应用程序的并行配置不正确完美解决方法
2019-03-10
【IntelliJ IDEA 2019.2】idea如何开启自动编译
2019-03-10
强大的文字处理器——Nisus Writer Pro
2019-03-10
如何轻松适应从Windows到MacOS的过渡！Mac新手入门指南
2019-03-10
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 461208098 位访客