Hello all, I am now attempting to solve the problem FLIPCOIN in the practice section, medium difficulty level. I am aware that a naive solution gets TLE... However, I also know that some sort of segment tree data structure can and needs to be used to process queries fast. Below is my naive and wrong (from the execution time point of view) code, that gives me a TLE:
What I would like to ask, if that is possible is either a very good and explanatory reference with examples to implement segment trees for a similar problem, or, something that would be even better, if someone with more expertise could provide some sort of "editorial" and provide me with tips along the way, so that I could implement a segment tree on my own, I would be very appreciated. The reason why I ask this is that sometimes, even after reading editorials I have some trouble implementing some new data structures and a more guided and step by step explanation would help me a lot... If I can do simple things, one at a time and end up with a segment tree implemented and understood on my own, i'd be very, very thankful :D Thanks in advance, Bruno asked 27 Jan '13, 19:08

Hello @betlista, Thanks for your response, but I'd actually prefer a more naive explanation (like if I was 5 y.o. really!) of this concept... Because, like graphs, sometimes I get a bit lost in the theory behind the concepts and totally fail at implementing them... So, several things:
If I want to write an efficient method to query over an array, something with a signature like:
where this function will return me (for this problem) the number of coins heads up between low and high, I will need a method update, like:
My questions are: What auxiliary data structures do I need to use/create,besides a tree, so that I can use these methods efficiently? How to create a tree in itself? For example, if our input array was called simply array, we know that, initially we have:
would this function for querying values be correct:
This is where I've come so far... Any help would be extremely useful, thanks in advance, Bruno answered 28 Jan '13, 03:05
no!!I dont think above query function is right!!It would take a lot time!!Instead of use Segment trees...Just subtract the no of heads coins from total no of coins below that node!!And just use some basic function on query and update!I guess this might help for reference http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
(26 Jun '13, 02:27)

There very similar question to yours  http://discuss.codechef.com/questions/2068/flipcoinssolutionsarentpublic . And probably the answer is exactly what you are looking for... Especially this sample problem is the same one. If there is still problem we can elaborate more ;) answered 28 Jan '13, 01:39

I really dont know much about data structs but i found my own way of solving such probs. I simply create two arrays, one for each element stored individually and other which stores result of 100 element in one block. While processing queries i use those those groups to make my program around 100 times faster to get AC :) Here is a link to my soln. answered 26 Jun '13, 11:48
