What is the best for Range Minimum Query …Segment Tree Or Mo Algorithm(Query square root decomposition)???
Segment tree will be O(logn) per quer,Mo’s algorithm will be O(sqrt(n)).
However is you use sparse table algorithm then you get O(1) per query with O(nlogn) preprocessing
Here is a beautiful explaination of this
Hope it helps
1 Like
What is the ‘best’ method may depend on problem specification, like the size of array, type of queries etc.
In case I mention update query, consider it to be point updates.
- If the problem says that the array size will be small (of order 10^3) the most effective way is to just store
the minimum of all possible range [L,R] in a 2-D array. Note, however that update operation may be costly, since every interval containing the given index will have to be updated, therefore the array must be static. - If the array on which RMQ is to be performed will remain static throughout, you can make use of a Sparse
Table which has a preprocessing time of O(nlogn), a memory complexity of O(nlogn) and a query time of O(1). Again note that updation will be costly.
Reference - http://www.geeksforgeeks.org/range-minimum-query-for-static-array/ (has been already mentioned once by @inovation123
To handle update+query, we have 2 methods.
- Use the Segment Tree ADT. Preprocessing is O(n) and memory complexity is O(2*2^(ceil(logn))). Both update and query will cost you O(logn), so it works well for order Q=10^5 and n=10^5 where Q=number of queries+updates.
Reference for segment tree - http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
This reference is for sum over a range. Converting it to RMQ is trivial. Nevertheless mention in comments if you face any sort of problem.
- Another method is to make use of Square Root Decomposition (also known as Mo’s Algorithm). In Mo, you decompose your queries into range of size ceil(sqrt(n)) starting from index 1 (1-based indexing). We store the result of each interval of size ceil(sqrt(n)) (preprocessing is O(sqrt(n))) and we make use of it to compute our final answer. Consider each interval to be a block. Then we have n/(ceil(sqrt(n))) number of blocks. Consider any query [L,R]. Identify in which block L and R reside. If L and R reside in the same block, just compute the minimum in range [L,R] using the brute-force method. We are guaranteed a complexity of O(sqrt(n)) in such a case (worst case number of basic operations will be of order sqrt(n)). If however L and R are in different blocks, consider the blocks that are in between blocks of L and R (that is, excluding blocks of L and R). If any such block exists directly take the value of RMQ of that block for computing the answer. After that all that remains is to find the minimum of the value of the blocks, and the values lying from L to the leftmost index of the first box, and from the rightmost index of last block to R (L, R and the two indexes are included). Again the query will be of order sqrt(n). So, query will be O(sqrt(n)) always! Update query is trivial. Just identify the block of the index and update the block, and update the original array.
For square root decomposition preprocessing and query is O(sqrt(n)) and update is also O(sqrt(n)) since you need to find the minimum for that block fresh. However this can be improved upon a bit, by checking whether the old value at index where update is taking place, holds the minimum value of the block or not. If not then update is just O(1). Therefore, it is kind of test-case dependent. Nevertheless O(sqrt(N)) update and query works well.
So it can be used interchangeably with Segment Tree for update+query type problems.
Reference for square root decomposition - http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/
Again this link is for range sum, and converting it to RMQ is trivial.
If you face any difficulty in understanding any part of my answer, feel free to comment.
Edit - Earlier I wrote that update query in Sqrt decomposition method is O(1). I have edited that part.
3 Likes