I was solving this problem (the one below) , i see that first two queries are possible with seg tree, but then how can we efficiently do the 3rd query ( i know it is possible using some other algos like sqrt decomposition but I wanted to solve this with a seg tree)
here’s the link to the problem
Hey @msatanzeel
store min and max of segment in each node, Do the 1st and 2nd query as you do with lazy propagation.
then for finding the first occurrence of z ,
make query function which checks if z lies in [min,max] of that segment, if yes then again check for first half of that segment if it lies there using above min-max interval
if yes then again do the same if no, the check in the second half of the segment, doing in this particular way, you will reach a segment of size 1 check if z lies in it, if yes then it will be the first occurrence of z, if you get no, then no occurrence of z is in the original array
you can similarly find the last occurrence of z by always first checking in the second half of the segment, then in first half you z don’t lie in second segment
I have a small doubt,
say suppose the array has 8 elements and it is as follows
1 8 1 8 1 8 4 4
Now if we get a query 3 as z=4,then as you said we will look in to segments (1,4) and (5,8).
As we see that our z lies in (min,max) range of left half we will go ahead considering it
to be our current segment, now again we have (1,2) and (3,4) . We will go ahead with
(1,2) and end up seeing that there’s no z!!! This is the counter example I found.By the way thanks for your response
You may say that while back tracking to go for the right segment if in case z doesn’t lie in left half, keep in mind that in worst case this will tale an order of n time !
bro, listen i was talking taking about the segments of segment tree,
like node v contains segment 1 to n
then i’m talking about segment of node 2v containing first half segment and 2v+1 containing second half segment.
so when you see there’s no z in [1,2], you will backtrack in query function in your ST, and return you didn’t find z until [1,4] then you will move ahead and check in [5,8] then in [5,6] and seeing negative again in [5,6] check in [7,8] then in [7,7] which contain z so its the first occurrence, means index 7 contains first z
let me see a little bit into it
Yaa, it’s O(n) in worst case.
If you could do range updates on merge sort tree in O(log) order, then it could be implemented in O((logn)^k) using binary search. but range updates on merge sort tree is not feasible i guess. 