皮蛋秀柚秋

笔记

读书笔记(2) 题解(1)

/ 注册

全部文章 / 笔记（共1篇）

RMQ算法

RMQ RMQ(range min/max query)区间最值查询算法。经典场景：给定一个数组A[1...N]，有N个数字。查询区间[l,r]，求该区间的最大/最小值。常规方法是对[l,r]进行遍历，复杂度O(n)。当查询次数K巨大时，性能会很差。RMQ算法需要nlogn时间进行预处理，之后以O(...

RMQ

2020-05-24

0 735