SPREAD - Editorial







Can be found here.


Can be found here.


still don’t get it…how do we add k from u to v…any hints

I am solving using BIT.
Here is my Solution.
Still getting TLE, I can’t find why.

can anybody elaborate the explanation
it’s hard to get the logic behind it

@doodle90 think about cumulative sum array. see this

@rsj1308 - In this question , suppose we want to update range [2 4] with value 1, thus first we call update(2) which will update node 2,node 4 and node 8(lets say length of bit array is 10) with value 1. Now call update (5) and this will update node 5, node 6 and node 8 but with -1. Now doing a point query will back trace all the node and the nodes which were not within the range get updated with negative number and that within the range gets updated with positive number. Once you back trace these will cancel out and gives you the correct result.

0 0 0 0 0 0 0 0 0 0 0

0 0 1 0 1 0 0 0 1 0 0 - Update(2,1) - update node 2 -> node 4 -> node 8

0 0 1 0 1 -1 -1 0 0 0 0 - Update(4+1,-1) - update node 5 -> node 6 -> node 8

get (6) -> node 6 + node 4 + node 0 = -1 + 1 + 0 = 0 which proves the above algorithm holds true.

1 Like

I used lazy propagation and I tested my program with many test cases i got correct ans but whenever I submit I got Wrong answer.

Can anyone tell me what is wrong in my code

Why does this solution give TLE? The logic is in accordance of Range Update, Point Query of a BIT.


Whereas when I tried the method of “fast input” (borrowed from someone else’s solution) it worked out perfectly fine.


Why is that?

1 Like

Its absolutely non-sense that this question can’t get AC without fast input output. Even with printf scanf and correct efficient algo it gets TLE’d and with fast input it gets AC.


Worst question on codechef.
Without fast input this problem can’t be solved

1 Like

Is TL of this problem still fixed?

1 Like

Good Question!! :smiley:

What is the reason behind “query(x) doesn’t return the sum of the elements having key less then or equal to x and update segment(u,v) with val = k is same as update(u,k),update(v+1,-k)”?

1 Like

Segment trees are usually meant for range queries, but here we are just interested in getting the value of one element.
update(u,k): add k to values for 1 to u
update(v,k): add k to values for 1 to v
So, to add k to range (u,v), you have to do update(u,k); update(v+1,-k).

There is problem with the formatting of test cases…

see http://www.codechef.com/viewsolution/6988353

why would update add from 1 to u it would add only to u

your ans§ will give the sum from 1 to p but we want only the p heap size

why in the query function we are doing query§ it will give the sum from 1 to p but we want only the value in heap p