nivin's blog

Finding kth largest element using Interval tree?
By nivin, 10 years ago, In English

Is it possible to findT kth largest element in the tree. With update and query operation ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes it is. (If I understood the problem right)

In nodes you should keep how many nodes are there already in the subtree. Lets call it size of the subtree. (size of parent is size of left tree + size of right tree)

Recursive Query goes like:

When you see your left subtree's size is > k, you check the left subtree, else you look in the right subtree for a tree of size k — size of left subtree

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

Suppose you are given numbers from 0 to n — 1, now you've to find the kTh element. (If the numbers are enough large, I'd map them with relative small numbers.)

In the interval tree, every node will contain how many elements are there in it's range. Now you can use binary search to find the answer. Here is the sample code:


struct node {
    int left, right; // for range, [left, right];
    int count; // number of element in the range

    node *left_child, *right_child;
}

int binary_search (int kTh) {
    node *x = root;
    if (x -> count < kTh) return INF;

    while (true) {
        if (x -> left == x -> right) return x -> left; // leaf node
        if (x -> left_child -> count < kTh) {
            kTh -= x -> left_child -> count;
            x = x -> right_child;
        } else x = x -> left_child;
    }
}

UPD: There is a simpler version of this interval tree. I know it by the name of 'misof tree'. Here is a sample code. I've changed the original code though but the basic idea is same.

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

    Would you please elaborate briefly how does this tree work? Or give a link to a paper or article if possible?

    Thank you

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I just have the code of misof tree, nothing else. So I'm going to explain as much as I can. It works in the same way as in the interval tree.

      A node contains the count of the numbers that are in it's range. Now when we've to insert a number, we start from the leaf, increment the count of the leaf and then climb up to its parent node. We continue this process until we reach to the root. Delete operation works in same way.

      A problem is that, it only works for numbers from 0 to n-1. So we may have to map the input numbers. Also the tree has to be perfect binary tree to make the searching work. So we've to choose a suitable value for the leaf such that leaf >= n and leaf = 2^x form.

      Suppose we've to find the kTh number. From a node, we should decide should we go to left or to right. If the left node contains equal to or more than k numbers, then left sub-tree contains the result, else the right sub-tree has it.

      I hope this explains.

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

    I am confused. In your code, the 4th line and 6th line both have same if condition. Is it a typo?

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

I have a N*sqrt(N)*log(sqrt(N)) solution. And it got accepted. How is this possible?

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

    It has a precomputation of O(N*sqrt(N)*log(sqrt(N))) and query time O(sqrt(N)*log(sqrt(N))). I was pretty sure while I was writing the code for this that this code would get a tle.

    → Reply