I know it can be solved using Binary Indexed Trees. I read them, but still haven't been able to find a solution. Can someone explains me the algo, please.... :) asked 01 Sep '14, 22:32

So let's start by creating 2 arrays that store the segment tree and the flag value for lazy update
The children of the current node in the segment tree are Initially those arrays will contain 0(all coins are kept tails up). Before understanding the update function, I am going to talk about the query function, lets assume that we have updated certain no of queries in our segment tree, then our query function is going to look something like this : Note : that this does not contain the lazy part.
node : it is the current node in the segment tree start : it is the starting index of our the coins we consider in the current node. end : it is the ending index of our the coins we consider in the current node. eg : if node = 1(i.e the initial node in the segment tree), then start = 0, end = N1. L, R : they are the indices of the query that we need to perform. As it is clear from the function we check the start and the end index if they are within the query that we need we return the current node, else we recurse furthur to the two children of the current node and return their sum. Now lets move on to the lazy update part :
So now while going down the segment tree if we find that a certain node has been set to 1, i.e we need to update it. Updating can depend on the question here update is easy we need to flip all the coins in the current range , i.e no of new heads = total coins in curr node  no of old heads. No we flip the flag value of the children of our current node. Note : The query part still takes the same time as the normal query would, we just check for lazy flag and accordingly manipulate our answers at the current node if needed. Now lets move to the update function.
The update function is pretty much like the query function we go down the segment tree update the no of tails in the current node(if within range) and go down until we reach the leaves of the tree. Now notice for a segment (L, R) to update we need to update (L, R) and all its corresponding children and their children and so on.... That is a lot of work going down upto the leaves of the segment tree and updating them, so the idea of lazy update is update the node when we need to and leave all its children the way they are, so for that we just need to have a flag value that remembers that we need to perform update on a certain node, we don't actually update the node untill we need to. So the update function with lazy propogation would look like :
Here the first if condition checks if the lazy node had been set previously or not. Then the 3rd if condition is where we check if we have found the segment in the range, and update this segment and instead of recursing down the tree all the way to the leaves we just flip the flag values of the children so if we were ever to query the children we could update them first and then return the answer. Note : we only need the queryLazy, updateLazy functions to solve the question the normal query and update were just to make the understanding simple. Also that the update part depends on the question and often can be quite complex. answered 02 Sep '14, 23:55
this is nice :) So my "highlevel" explanation is not very wrong :D
(03 Sep '14, 00:38)
@u_seem_surprsd, what is the node passed to the query and update functions when we call them? Do we use the value of the start point of query as node? I really want to use this pseudocode along with both our explanations to finally crack this and also build several topics with detailed solutions for other problems here and on SPOJ, maybe this will be possible with your help
(03 Sep '14, 17:02)
@kuruma whenever we make an update or query we give the starting node of the segment tree eg :
here the node keeps track of intervals, and when querying we go down the tree looking for the interval we need. link to my solun : http://www.codechef.com/viewsolution/3968902
(04 Sep '14, 00:03)
Thanks a lot, this is slowly starting to make sense :D
(04 Sep '14, 03:11)
CAn anyone explain why have we done this ? ST[node] = (endstart+1)  ST[node]; I understand we are updating the seg tree here but why are we subtracting the value (end  start +1).
(25 Dec '15, 01:20)

@stasszczesniak why don't you try to explain it trough here so everyone can learn a few new things? I have a very hard time and difficulty with coding Segment Trees myself, but, to solve this problem, you basically need two things:
Like I said, I have read many, many things on segment trees but, never really could implement them properly on my own, so this will be a somewhat theoretical explanation... If something is wrong, please try to correct it. First of all, it matters to say that segment trees are For the sake of an example, let's consider just a static array where single updates are performed. How would we go about solving this problem in the first place? It's not so hard if we are aware of the basic strcture of a segment tree and if we can map this into something we are familiar with. Let's consider now the static array with the following coins, where H means heads and T means tails. [H, T, H, H, T, T, T] (note: this is actually one of the things I can't seem to know how to fix, but, when the original array you have has a size which is not power of 2, I don't really know how to build up all the nodes.) If we want to count how many coins in a range are Heads up, we can map this into a well known problem for segment trees: If Heads = integer number 1 and Tails = integer number 0 then the answer we are looking for is simply the sum of all numbers in range (A,B), right? Then when building the "internal" nodes of the segment tree, this is the info we will store on the nodes: the sum of its descendents. We now have: [1, 0, 1, 1, 0, 0, 0] To build the tree, we group the nodes in pairs, recursively storing the desired information on the new nodes:
At each level we have the sum of the 2 elements which are below it, with the last 0 being "carried up" since the size is not a power of 2. Not sure if this is correct. Let's assume our original array is indexed from 0 to 6. We now have query(2,6). Answer is 2. Instead of going trough the 5 values on the original array, we can go up in the tree. Why is this better? Well since a binary tree built over N nodes has height of at most log2(N) then it takes us time at most log2(62+1) to answer our original query. A lot better than 62+1 dont you think? How the "go up in the tree" is done in practice still confuses me a bit, to be honest, but, at least this makes sense to me so maybe it makes sense to you too. Now, as you see, if we change a single value, we can simply change it on the original array and then update only the internal nodes on which this update is going to reflect, taking us log2(N) time to "reset" the tree for a single update. EXAMPLE: we flip coin 5, so now original array is: [1, 0, 1, 1, 0, 1, 0] After the update of the internal nodes we have now (notice that the updated nodes are in bold):
On this problem, we have a range which can be updated instead of a single element. Based on the above drawing you can see now that when updating a range the main problem we face is that on the higher levels of the tree, an internal node can be updated several times. As such instead of performing multiple updates to a single internal node (like you know, doing several single updates multiple times which would take linear time on the number of updates) we can mark some of the nodes as lazy. We do this presumably from all I've seen, by adding a flag on each node which marks the number of times it will be updated and then according to the values of these flags we go up in the tree one more time and update all the nodes taking still logarithmic time to update a range (maybe this is total bullshit idk really). How to implement this....No idea....What can I say I'm a theory kind of guy xD I've been lately reading and rereading this over and over: http://discuss.codechef.com/questions/49339/equakeeditorial but, I still haven't managed to code anything on my own... Hope this can help you or at least motivate someone more skilled to add some insights to this... Best, Bruno answered 02 Sep '14, 20:20

Hi,
Cheers! answered 23 Mar '17, 16:39

Hey, Could someone please help me, I just read about segment tree and did this problem using segment tree. But I am getting time limit exceeded. Here is my code: http://code.geeksforgeeks.org/7dCRT4 Thanks in advance. Vipul answered 27 Mar '17, 17:06

Hello all, Can someone please help me with some sample test cases to test this code with? I tried lots of test cases but I can't seem to get it accepted. It appears to pass all the cases I have designed. https://www.codechef.com/viewsolution/16573912 Regards, Ruddra answered 14 Dec '17, 21:50

Ok. answered 01 Sep '14, 23:52

Hi. answered 02 Sep '14, 23:12

CAn anyone explain why have we done this ? ST[node] = (endstart+1)  ST[node]; I understand we are updating the seg tree here but why are we subtracting the value (end  start +1). answered 25 Dec '15, 01:26

we are subtracting because we want to get the total no. of elements in the range. answered 23 Mar '17, 13:38

@shubham99 This denotes the flipping of coins in range. Like it's already stated answered 04 Apr '17, 08:47

Can anyone plz help me out..i am getting time limit exceeded here is my code https://www.codechef.com/viewsolution/15551011 Thanks in advance. answered 29 Sep '17, 15:08
