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
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.
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
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.
Okay okay… Got that… Ya we can I guess…