rr459595's blog

SPOJ Segment tree problem (TEMPLE queues)
By rr459595, history, 7 years ago, In English

Link to the problem :- http://www.spoj.com/problems/TEMPLEQ/

In this question for answering type 3 queries where we have to update the nodes with value greater than x, we create a segment tree and do lazy propagation. In segment tree, internal nodes are maximum of left and right child.

For answering type 1 queries (updating), I need the last index of a particular element. If array is 1 2 2 2 2 5, last index of 2 is 5.

My question is how can I find the last index of a particular element using binary search in the above segment tree (where internal nodes have max of left and right child) in O(logn) time instead of O(log2n)?

Thanks.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

You don't need to perform an additional binary search. If you have the correct information in the nodes, one query on the tree is enough.

You need to keep, not maximum of left and right children on each node, but first and last element of this node. You know the tree is sorted and you have first and last element for every node, so say you're looking for the last occurrence of element x: if first element of right child is  ≤ x, then go to right child, otherwise go to left child. Keep doing that until you reach a leaf. That's the index you're looking for.

Note: Last element is also needed, for the case when you need to find the first occurrence of an element.

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

    This basically is binary search, but yes, an implicit one, not explicit. Thumbs up

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

    So silly of me :( . I actually had max of internal children stored in the node for updating nodes based on threshold. I will add one more field to the node now to perform binary search. Thanks !

    → Reply