supercharger's blog

Range Minimum Query, For Top 2 Min Elements in single range
By supercharger, 10 years ago, In English

Can we tweak RMQ for finding Top 2 or 3 Elements with in a single range ( like using another Data structure to augment) .

A Naive RMQ algorithm looks like below, 

//M[][][0] contains the top min element, and M[][][1] is the second min
private void computeRMQ(int M[][][], int A[], int N) {
		for (int i = 0; i < A.length; i++) {
			M[i][i][0] = i;
			M[i][i][1] = i;
		}
		for (int i = 0; i < A.length; i++) {
			for (int j = i + 1; j < A.length; j++) {		
				if (A[M[i][j - 1][0]] < A[j]) {
					M[i][j][1] = M[i][j][0];
                                        M[i][j][0] = M[i][j - 1][0];
				} else {
                                        M[i][j][1] = M[i][j][0];
					M[i][j][0] = j;
				}
                                //some cases ignored
			}
		}
	}

But, for the Can you help with any pointers for the standard O(N), O(logN) implentation....

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Well, for both static RMQ and dynamic RMQ (segment tree) you have something I'd like to call "the merge function". It's basically the case when you have the values computed for two intervals and you want to compute the value for the whole interval formed when you merge those two.

So if we're gonna change something it'll be the merge function. Let's suppose we are merging interval A, with interval B and we want to create the values for interval C (which is the merge of A,B). In regular RMQ we'd have:

C.min_element = MIN(A.min_element, B.min_element)

So let's extend that to two numbers. What happens then is that we actually have "A.firstmin,A.secondmin,B.firstmin,B.secondmin" elements and we want to get the two smallest elements in C. Well, whether you'll do it with some if statements or some other way, you basically have to pick the two smallest elements among four elements.

It's easy to see that this can be extended further as much as you'd like. If you want the top N elements, then A and B will both hold N elements, making a total of 2N. Then from those 2N you'll want to pick the N that are smallest, which is simplest done by sorting them, so O(NlogN) complexity for merging two intervals.

In the cases where you want just 1,2,3 smallest elements you can use naive methods of merging as it's just 5-10 operations anyway.

Hope I helped :)

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for the reply, It makes a lot sense. But, I am asking for the Top 2 min elements within a single range.

    I am not aware of the merging interval, Can you please point to some resource or any code.

    PS: I updated the blog post with some naive implementation.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      This is how to merge two nodes in segment tree.
      Every node has min and second_min variables.

      node merge(node a, node b) {
  // We have 4 values: a.min < a.second_min && b.min < b.second_min
  // So the minimum of 4 of them is a.min or b.min
  node c;
  if (a.min < b.min) {
    c.min = a.min;
    // We have 3 values left: a.second_min && b.min < b.second_min
    // So the minimum of them is a.second_min or b.min
    c.second_min = min(a.second_min, b.min);
  }
  else { 
    // Same here
    c.min = b.min;
    c.second_min = min(b.second_min, a.min);
  }
  return c;
}

      Here you can see whole segment tree: pastebin

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I'm not certain what you want. I assumed you want a RMQ for finding the 2-3 smallest elements implemented in O(NlogN) and my idea explains that. If you have trouble with the basic O(NlogN) RMQ you should look at some codes and blogs, there are tons of them.

      The idea of "merging" is not really some method or anything, it's just a basic part of the O(NlogN) RMQ, and I'm sure you'll understand what my comment is saying once you learn the O(NlogN) RMQ for 1 element :)

      P.S. Na2a showed precisely what I meant by the merge function, so you can see the idea from his code (in this case, dynamic RMQ)

      P.S.S In addition to my previous comment, if you want to merge two nodes carrying K values, it can be done in O(K) since you don't need to sort them. They are basically two sorted arrays so you can just walk with two pointers and add the smaller element until you get K elements.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

RMQ

→ Reply