Tanmoy1228's blog

Binary Index Tree or Segment Tree Problem
By Tanmoy1228, history, 9 years ago, In English

Problem: Light OJ — Lining up Students

can anyone give me any idea

how can i solve this problem with Binary Index Tree or Segment Tree???

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

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I used Segment Tree(ST) to solve this problem, it stores the number of available id's in each range.

You start it with all id's as available ( Build() ) and for each student, from right to left, you set 1 id as unavailable ( Update() ). Query(i) will return the ith larger id available.

If you still need help this is the code I used: Don't click me.

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

    please explain how it works....

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

      Consider S[i] as Student in position i. Suppose that the input is organized in a vector A, where A[i] means the number of students who are taller and are on the left of S[i].

      A[i] means that S[i] is the (A[i]+1)th taller in the subarray S[0 to i], and that's why you process the students from right to left. You can't process from left to right because you don't have enough informations about who's on the right of S[i].

      Then you should for every S[i] find what is the (A[i]+1)th larger id available. Here is where the ST is used.

      How the ST works:

      Each interval [s, e] in the ST has an associated value that means how many available id's exist in this interval.

      When querying to find the position of the ith id, the current node will look at it's right child. Suppose that the right child has x available id's, if x >= i it means that the ith larger id is in the right child. If x < i then the ith id is in the left child. If the current node has no children it means that itself contains the ith id.

      After finding the position of the ith id it's needed to set this position as no longer available. Just deacrease by 1 the value of all the nodes with intervals that contains this position.

      Maybe an example of how it works is better: Testcase: 1 \n 5 \n 0 1 1 3 1

      P[] = Values in the leafs of the ST | Res[] = Id's of students

      Step 1: P = [1 1 1 1 1], A[i] = 1 | Second larger id is 4. Res = [-1 -1 -1 -1 4]

      Step 2: P = [1 1 1 0 1], A[i] = 3 | Fourth larger id is 1. Res = [-1 -1 -1 1 4]

      Step 3: P = [0 1 1 0 1], A[i] = 1 | Second larger id is 3. Res = [-1 -1 3 1 4]

      Step 4: P = [0 1 0 0 1], A[i] = 1 | Second larger id is 2. Res = [-1 2 3 1 4]

      Step 5: P = [0 0 0 0 1], A[i] = 0 | Larger id is 5. Res = [5 2 3 1 4]

      Output: 5

      → Reply