标签：RMQ 笔记 st ST 区间 长度 数据结构

ST表

RMQ 问题

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。
ST 表是用于解决离线 RMQ 问题的一种线性数据结构，在全国青少年信息学奥林匹克系列竞赛大纲中难度为 6，是提高级中学习的数据结构。

倍增思想

考虑每个长度为 2 的正整数幂的区间，这个区间的最值可以分为左右两个长度相等的区间，同时这两个区间的长度又是 2 的整数幂。
所以，我们可以从小到大来递推处理出所有长度为 2 的正整数幂的区间的最值。
形式化地，以最大值为例，记 \(st[i,j]\) 表示以 \(i\) 为左端点，长度是 \(2^j\) 的区间（区间\([i,i+2^j-1]\)）的最大值，分为左右两个长度相等的区间，则有

\[st[i,j]=\max(st[i,j-1],st[i+2^{j-1},j-1]) \]

边界条件是 \(st[i,0]=a[i]\)，据此递推即可。（\(2^0=1\)）
时间复杂度为 \(O(n \log n)\)

标签：RMQ,笔记,st,ST,区间,长度,数据结构
From： https://www.cnblogs.com/JXOIer-zaochen/p/17029398.html