### Mode can be easily found using a segment tree with max queryâ€¦ having a leaf node containing frequency of elementâ€¦

### Moreover median can be found using segment tree for sum queryâ€¦ Having a leaf node containing frequency of each elementâ€¦

#### You also need a sum of frequencies for Segment **[1,l-1]** which is again O(logn) for segtreeâ€¦

Now u have sum of frequencies from starting to **l-1th** elementâ€¦

As well as sum of frequencies in segment **[l,r]**

Now Hence you know where from starting your median will be there (do ask if u donâ€™t know that)

### Hint :

## Click to view

It will be there in middle of [l,r] so you will find it at **(freq(1,l-1)+((freq(l,r)+1)/2))th** number from startingâ€¦

### OR

median is average of **((freq(1,l-1)+(frequency (l,r)/2))th** element + element after that

##(Yes , depending upon frequency%2)

Now you know that it is at (letâ€™s say) **kth** element from startingâ€¦ if we make a real list using frequencies but you canâ€™t

make one due to bounds of space and timeâ€¦ So,

### Again a log(n) approach for getting kth element from starting using segtree tree (sum query tree) we madeâ€¦

recursively check

` if k<= SumFreqency_LeftNode getElement(leftNode,k); else getElement(rightNode,k-SumFreqency_LeftNode) `

Something of this typeâ€¦

Feel free to ask queriesâ€¦

Thanks

So basically 4 times O(log(n)) things to do for each queryâ€¦

@l_returns for finding median canâ€™t we just apply Binary Search for the Sum(0, L-1) and Sum(0, R). That is just looking for the first element in L, R whose sum is either greater than or equal to the required. The time complexity will be [log(N)]^2.

It may also be solved by using sqrt decomposition(Code will be shorter than segment tree)

Decompose the whole array of size N into \sqrt{N} blocks of size \sqrt{N}.

Now, preprocess the array to store i for which A[i] is maximum, and the sum of elements in that block, for each block which can be done in O(N) by just traversing the array once.

Query: For mode i.e index i for which A[i] is maximum, observe that any range [L,R] can be broken into few complete blocks (\leq\sqrt{N}) and two or less partial blocks. You know the value of sum and A[i]_{max} for complete blocks and for partial blocks you can just iterate and calculate. You will need at max 3$\sqrt{N}$ iterations. By using sum you can find median and i for A[i]_{max} is mode.

Update : just update the sum and i for A[i]_{max} just for the block in which i lies. Complexity O(\sqrt{N}).

Total Complexity for algorithm is O(N + Q\sqrt{N}).

Ps : I didnâ€™t try this approach during contest but mentioning it as an alternative approach.

Okay okayâ€¦ Got thatâ€¦ Ya we can I guessâ€¦

I am getting TLE. I donâ€™t know why?

I have made two segment trees : one for finding the maximum and other for finding the sum and in that range.

I have used some binary search sort of thing to find the median.

Here is my code :

https://www.codechef.com/viewsolution/18897277

please someone help me in figuring out the bug