【求助】RMQ问题ST算法

k:=trunc(ln(r-l+1)/ln(2));
ans:=max(F[l,k],F[r-2^k+1,k]);
把k带进去后
r-2^k+1等于l，那max还有什么意义。。。不知道是不是k计算的时候要这样做。。望大牛解惑。

向下取整了，不会相等的，把一个区间拆成两个区间的并，这两个区间是有交集的。弱菜的理解就是这样。

是的。。瞬间了解

你没理解ST的思想

那啥。。你这样空间不就N^2了么。。。

不仅是节省空间如果你那样做的话显然预处理也是平方级的

ST就是因为采用了二分和归并的思想所以做到了对数级别，如果你这样设计状态，递推的时候就要穷举分点，无法达到如此高的效率。
ST的思想满精髓的

下载贴吧APP
看高清直播、视频！

分享到: