algorithm - 段树中的存储时间

我想知道一个用于解决范围最小查询问题的段树中有多少节点。
另外，构建操作需要多长时间？为什么？

最佳答案

如果使用段树，那么build是O（nlgn），每个查询都是O（lgn）
如果数组是静态的，你也可以尝试另一种算法RMQ构建时间为O（nlgn），每个查询仅为O（1）。