can someone explain this part of the editorial of Forbidden Sum of January Long (http://discuss.codechef.com/questions/35346/frbsum-editorial)
“For the static Segment Tree, we can maintain a sorted list in each node with their prefix sum (O(N log N) space is needed, because there are O(N) numbers stored in each level). When the query covered the whole interval stated by the node, binary search is adopted to fast locate the “x <= S + 1” position and return the prefix sum. Therefore, we can solve each query in O(log^2 N) time”
same doubt here please someone respond
for each node of the segment tree having interval [L,R] we keep the interval [L.R] in sorted form and store the prefix sum. Now for every query l,r we initialize the ‘sum=0’ and we do binary search in each node of the segment tree which lie in the range l,r and return the sum of all numbers which can be obtained by compairing the current ‘sum’ that can be obtained and update ‘sum’ to this returned sum. we repeat this step untill their is no change in the value of ‘sum’.
You can see my solution hope u will understand http://www.codechef.com/viewsolution/3256097
1 Like
Have a look at my
(http://www.codechef.com/viewsolution/3279893). Hoping it will help you.