Was trying to solve http://www.spoj.com/problems/FREQUENT/ and since was unable to figure out so finally looked at the solutions https://github.com/hbdhj/spoj-cpp/blob/master/1684_FREQUENT.cpp

There I was unable to figure out what was being done in line 127 :-

““int temp = min(Tree[Node<<1].rfreq, m-u+1) + min(Tree[(Node<<1)+1].lfreq, v-m);””

kindly explain… Though I know that here the mf was being calculated by using the leftnode.rf and rightnode.lf but what was the “m-u+1” & “v-m” was doing???

Suppose you have an **array A of N elements**, indexed as 0, 1, …, N - 1 then consider a **query (I, J)**, that is finding most frequent element between index I and J, both inclusive. Now there are 3 cases with respect to **mid index M = (I + J) / 2**

- Index J is on left side of Index M.
- Index I is on right side of Index M.
- Index M is in between of I and J.

Now for first two cases you can go with querying one side of Index M, but if Index M is in between the index I and J then we need to compute **most frequent element of left part [lfreq]** and **right part [rfreq]** and then we have to check whether **values at Index M and (M + 1) are equal or not**.

If values are different then **answer to query is maximum of lfreq and rfreq**, but if values are same then we need to check whether the **second last element of left part of array A[M - I + 1]** and the **second element of right part of array A[J - M]** are different from the **values at Index M and (M + 1)** respectively.

To do so, just check whether the **second last element of left part** of array is **smaller than rfreq** and similarly verify the same for **second element of right part** of array and **lfreq**, and once we have the minimum frequent elements of left and right side of array, check whether the **previously computed frequent element is greater or the temp frequent element**, then just **return the maximum** of the two values.