Month: March 2019

众所周知，ST表是一种离线解决RMQ(区间最值)问题的方法。 可以在O(n \log {n} ) 的时间内进行预处理，然后在O(1)时间内查询到结果。 复习一维 我们先来复习一下，一维st表的预处理和查询过程。 对于预处理，我们先定义一个名为st的二维数组，其中st[i][j]表示以i为起点，从起点开始（含起点）往后2^j个元素的最值。 满足i+2^j-1不越界 因为2^0 = 1 ，因此st[i][0]=a[i] 然后我们用2个for循环去打表就行了 接着是查询，这里我画了个图来解释。 其中橙色的线表示两个区间。 一维代码…