Today's test I was asked to a question and I wrote brute force solution but it gave me an TLE. I want to know the optimal approach for the question. Given an Array of size N, you will be given an integer Q, which represents the no.of.queries will be given. Each query will contain two integer {L, R} where L and R represent the range of integers in the Array. You need to find the median for each query in the given range {L, R}. CONSTRAINTS: 1 <= N <= 1e5; 1 <= Q <= 1e5; 1 <= L <= R <= N;
Merge tree + bin search, log^3 (awful).
You could use Mo's algorithm combined with using two ordered multisets to track the left half and right half of your items in the active range.for time complexity $$$O(n\sqrt{n}\log{n})$$$.
Can be done by using persistent segment tree in $$$O(Q\log n)$$$
Thanks for the your help. Could you give the reference link for the ease of understanding?
Sure: https://cp-algorithms.com/data_structures/sqrt_decomposition.html#mos-algorithm
You only need to use the vjudgian algorithm and open a black hole
Can be done in O(N log N) preprocessing and query using a Trie of decimal digits as string and store index of inserted values in each node in increasing order.
Then, for [L, R] query we find the Kth smallest element (K = (R — L + 1) / 2 for median), in trie using this https://codeforces.net/blog/entry/104650
but to simulate a trie with only elements in [L, R], we binary search the count of indexes in [L, R] while traversing a node, which acts as frequency of that node and then we use Kth smallest in trie technique as mentioned in linked blog.