I am trying to solve this problem RRANGE but cannot get an efficient approach with segment trees. I know I have to build the segment tree for the difference sequence but am unable to frame the complete logic. Can anybody help me to solve this one ?

Refer this Topcoder tutorial for segment trees.

1 Like

I have already read that tutorial earlier. But in this problem the update is in the form of an arithmetic progression which is different from what is dealt in the link. I want to know how to perform these kinds of range updates which is not mentioned there.

Similar problem: Lightoj 1411
Tutorial: http://lbv-pc.blogspot.com/2012/11/rip-van-winkles-code.html

@dumdhead there is no need to know segment tree to solve RRANGE think differntly this can be solved by simply storing the upper and lower bound of the range…as the value of N can be upto 10^9
segment tree is not a good choice

@dumbhead take it easy yaar, every range update questions are not solved by segment tree :stuck_out_tongue:
and here u can’t even make segment tree for the range 1-10^9
it can be solved easily in O(q*u) by checking every updated range for each query