orchidmajumder's blog

By orchidmajumder, 9 years ago, In English

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.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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) / 2

and 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!

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

    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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You ca solve it with sqrt decomposition

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

    could you explain a little for solving with that method?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I added this question on Quora.The answer by utkarsh explains it very nicely. Quora answer link