ST表

admin

ST表是一种用于解决RMQ(Range Minimum/Maximum Query,即区间最值查询)问题的离线算法，与线段树相比，预处理复杂度同为O(nlogn),查询时间上，ST表为O(1),线段树为O(nlogn)

st表的主体是一个二维数组st(i,j)，表示需要查询的数组的从下标i到下标i+2^j - 1的最值，也可以理解为从i开始长度为2^j个数的最值，这里以最小值为例，假设原始数组A={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
那么



P1816 忠诚  http://hsyit.cn/forum.php?mod=vi ... &highlight=1816

P3865 【模板】ST表 http://hsyit.cn/forum.php?mod=viewthread&tid=69268