Comparing Data Structure
Both the Sparse Table and Segment Tree are data structures that can answer the Range Minimum Query. It's not right to say that which is definitely better than the other because it depends on the circumstances.
Let the number of elements be and the number of queries be . Given that that , which data structure should we apply?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The time complexity for a Sparse Table and Segment Tree is O ( n l g n + q ) and O ( n + q l g n ) respectively. Both runtime increases linearly as q increases, but for Segment Tree there is a l g n factor. Since q is significantly larger than n , the construction time could be neglected, hence Sparse Table will work better.