# How to solve KRILLIN

### 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â€¦
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.

2 Likes

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