RMQ(区间最值查询)问题有多种解决方法,用线段树和ST解决RMQ问题的对比如下:
· 线段树预处理的时间为 O ( n log n ),查询的时间为 O (log n ),支持在线修改;
· ST预处理的时间为 O ( n log n ),查询的时间为 O (1),不支持在线修改。 BvWxuRrSfl0CEwHBX04ObYHl8dsG2FuOOSlbGbVK81O1PGveRAd2E9V3I9E356qe