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!

You ca solve it with sqrt decomposition

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