RMQ算法介绍
RMQ算法全称为(Range Minimum/Maximum Query)意思是给你一个长度为n的数组A,求出给定区间的最值的下标。当然我们可以采用枚举，但是我们也可以使用线段树来优化，复杂度为(nlogn)，但是最好的办法是采用Sparse_Table算法，简称ST算法。他能在进行(nlogn)的预处理后达到n(1)的效率。下面来分析下最大值和最小值，都要用到DP的思想。
二、RMQ应用
- 一维静态RMQ
- 二维静态RMQ
- RMQ+LCA
微信扫一扫 本文网址：https://www.zhankr.net/141292.html
相关推荐
python开发_常用的python模块及安装方法
adodb：我们领导推荐的数据库连接组件bsddb3：BerkeleyDB的连接组件Cheetah-1.0：我比较喜欢这个版本的cheeta…
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…
还没有评论呢，快来抢沙发~