SPOJ Segment tree problem (TEMPLE queues)

Revision en5, by rr459595, 2018-04-19 11:34:32

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English rr459595 2018-04-19 11:34:32 18
en4 English rr459595 2018-04-19 11:33:17 2 Tiny change: 'of $O(log^2n)$?\n\nTh' -> 'of $O(log^{2}n)$?\n\nTh'
en3 English rr459595 2018-04-19 11:32:53 24
en2 English rr459595 2018-04-18 09:00:07 42
en1 English rr459595 2018-04-18 08:58:57 635 Initial revision (published)