algorithm - 段树的存储时间

Question

我想知道为解决范围最小查询问题而制作的段树中有多少个节点。

另外，构建操作需要多长时间，为什么？

Answer 1

段树复杂度：

1. 一一初始化元素：O(NLogN)
2. 从数组初始化：O(N)
3. 查询范围：O(logN)
4. 插入（更新）元素：O（logN）

Answer 2

如果你使用段树，构建是 O(nlgn)，每个查询是 O(lgn)

如果数组是静态的，你也可以尝试另一种算法RMQ。构建时间是 O(nlgn)，每个查询只有 O(1)。