Equalizing Pillars

It is easy to prove that for a given range $[L,R]$ the best answer comes when we make the pillers height = $\frac{R-L+2}{2}^{th}$ element after sorting the range.

So the task is very simple. You have to find the middle element after sorting the $[L,R]$ elements. If you use merge sort tree it will find the middle element in $\mathcal{O}(\lg{N}\times \lg{N}\times \lg{N})$. To process $Q$ queries it will take $\mathcal{O}(Q\times\lg{N}\times \lg{N}\times \lg{N})$.

We can reduce the complexity to $\mathcal{O}(Q\times\lg{N})$ by using Persistent Segment Tree.

Time complexity: $\mathcal{O}(Q\times\lg{N})$

Memory complexity: $\mathcal{O}(Q\times\lg{N})$