Hey, here’s my segment tree AC solution. - https://www.codechef.com/viewsolution/13447911
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!