storage time in segment tree

Question

I want to know how many nodes are there in a segment tree made for solving range minimum query problem.

Also, how much time does the build operation take and why?

Answer 1

Segment Tree Complexity:

1. Initialization one by one elements: O(NLogN)
2. Initialization from array: O(N)
3. Query range: O(logN)
4. Insert(Update) element: O(logN)

Answer 2

if u use segment tree, build is O(nlgn), each query is O(lgn)

if the array is static, u can also try another algorithm RMQ. build time is O(nlgn) and each query is only O(1).