### orchidmajumder's blog

By orchidmajumder, 9 years ago, I want to ask how to apply a segment tree in a question like where instead of updating a range [a,b] by a constant v,we are told to update the range in such a way that i is added to i th box in the range [a,b] ,i=1..(b-a+1).

say,for example,this problem in SPOJ.

Impossible Boss

Any pointers will be appreciated.If there is any approach other than seg tree,I'd like to know that also.  Comments (5)
 » The only idea I could think is do something like this (using lazy propagation obviously): when you have to flag a node, flag using the corresponding value to it (if isn't flagged). if the node have a flag, flag its children with the corresponding value Let look an expample, suppose you make a tree with size = 8, the query is to add a value in [0, 7], you put a flag to the node watching the whole range (1 in my case) and its value for the buffer is the first value (1 in this case). the node 1 ( [0,7] ) has a flag (1).now you have to update the [0, 7] again, you go to node 1 and you could see that it have a flag, then, you go down and put a flag to node 2 ( range [0,3] ) with value 1, and for node 3 ( range [4, 7] ) the buffer should have 5.now you have to recover the value from [0, 3]: you check the node 1 and it have a flag, remove it adding to its real value the resulting value from a function f(), where f will receive a range [l, r] and a startng value (which is in the buffer), and return the sum from all the numbers from l to r starting from value, lets look an example in java:long f(int left, int right, long v) { return ( ( right * (right + 1) ) >> 1 ) — Math.max(0, ( ( left — 1 ) * (left) ) / 2 ); }it uses a formula, the sum from 1 to N is N * (N + 1) / 2and set a flag to node 2 (range [0, 3] ) with value = 1, and the another one to node 3 (range [4, 7] ) with value = 5, but both nodes were previously flagged, the you have to go a level down to flag using the same meaning.I think it should work in c++ (I not sure for java), that's not all, you have to get control when you cant flag to a child doing for example, unflag it and set the new flag, I hope this could be useful for you, its only an idea, I'll trry to do it later.Great problem!
•  » » I think the idea is good.I'll try to frame the complete algorithm based on it.Let's see if I can get it done.
 » You ca solve it with sqrt decomposition
•  » » could you explain a little for solving with that method?
 » 9 years ago, # | ← Rev. 2 →   I added this question on Quora.The answer by utkarsh explains it very nicely. Quora answer link