Hi All,
I am trying to understand the editorial, got most of it but I am still having a hard time to understand the segment tree part. Can anybody elaborate on what information does each node of the segment tree is storing? And what exactly do we query when we give a range of length k? What’s the relation between frame size k and information stored in the node of the segtree?
Thanks for your time.
Hey, here’s my segment tree AC solution. - CodeChef: Practical coding for everyone
In here, what I’ve done is this -
Initialize an array (called “dp” in my solution) which holds the maximum number of 1’s for any given window. (i.e dp[i] stores the number of 1’s for indices A[i-k] to A[i])
Now, each node in the segment tree holds the maximum number of 1’s in the node’s corresponding range.
My logic here was that my segment tree was constructed to answer every query directly, therefore every node must hold an answer for a set of certain ranges I have preprocessed query results for.
Thus a node on the segment tree stores the maximum value of dp in that given range, and a query checks all necessary nodes on this segment tree to find the global maximum for the given input range.
I hope this clears your problem! 
Try this :
This is excellent. Made it absolutely clear. ‘Maximum value of dp’ was ah ha moment for me. Thanks! 