MXDIST - EDITORIAL

vivace_jr · January 20, 2019, 12:48pm

If we can use merge sort tree type thing to merge to hulls why do we need RMQ then why cant we use segment tree to answer the queries?

vivace_jr · January 22, 2019, 1:19am

WHY do we need a RMQ, can we not simply solve queries using merge sort tree?? @taran_1407

taran_1407 · January 22, 2019, 2:55am

Because using segtree, we shall have to merge logN hulls (logC hulls if using sqrt dec). But by RMQ, we need to merge only two hulls (three hulls if sqrt dec, border block elements). Using segtree would increase per query complexity by log(N)