PROBLEM LINK:Author: Constantine Sokol DIFFICULTY:Medium PREREQUISITES:Segment Tree, Binary Search, Persistent Segment Tree. PROBLEM:Given A[1..N], and M queries about what is the smallest number that can't be represented by the sum of some subset of A[L_{i} ... R_{i}] (so called forbidden sum). EXPLANATION:First of all, we need to know how to process a single query. That is, given a set of number, determine the forbidden sum. Consider a special case, the answer should be 1 if we have no ones. Based on this observation, we can firstly sort the number ascending. Take the numbers one by one while maintain a sum S (initially S = 0). The algorithm is as following:
Suppose we have the next number x. If x is greater than S + 1, because of the numbers are ascending, S + 1 will be never got. Therefore, there is a break. Otherwise, 1 .. S + x are all possible. And also, we can describe the algorithm in an alternative way (but helpful):
we should observe that, the answer is smaller than the sum of A[1..N], <= 10^9, denoted as P. Moreover, S is increasing exponentionally, as fast as the Fibonacci Number, because the newly added number should be greater than previous loop's S. Therefore, there will be only O(log P) loops. Back to the original problem, for a given query, if we can fast perform the "newS = the sum of {x  x <= S + 1}" in the given A[L .. R], such as in O(log N) or O(log^2 N) time, then we can solve this problem. Fortunately, we can ask Segment Tree for help. 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. Furthermore, we can try Persistent Segment Tree to solve this problem in O(log N) time. Persistent Data Structure can help us to deal with the L .. R query into the delta of 1 .. R query and 1 .. L  1 query. Therefore, we can build the Persistent Segment Tree on their values (each node stands for an interval of values of A[]) and insert the A[i] from i = 1 to N one by one. After that, we can have N + 1 roots stand for different prefixs (ranging from 0 to N. 0th is an empty tree, ith is the segment tree after inserted A[1..i]). Each node this time stores the total numbers have been inserted in to this subtree. For a given query [L .. R] and the S we maintained, we query the total number <= S + 1 on the Rth tree and (L1)th tree, and then get the delta. This process is O(log N). Finally, using the Persistent Segment Tree, we can solve this problem in O(N log N + M log P log N). AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Jan '14, 15:11

Since I'm using java, I was very surprised to have one of the fastest implementation here, while I had a very bad worst case. Since I'm not too familiar with the presented datastructures I found myself another way, which I think is not very hard to implement. Note: Understanding the first part of the editorial is also required to understand why this is working. First preprocessing:
Handle queries: We can further use this datastructure by summing up per log2 value, starting of course by 0th group. Always adding up all the sums in the interval while the total sum at least is the minimum value for the group being 2^b (
This still is very fast but we may miss some numbers because we can reach higher group with one of the lower numbers in the group. E.g:
Therefore I used a naughty trick (maybe u've noticed the find method), scanning in the interval of the list that we also created in the preprocessing part. Remember that this is per group and we can also use binary search to quickly skip to the interval since we used ids. If there exists a number which is smaller or equal to the current total we continue the loop, adding the sum (trivial if you understand). It's probably so fast because it handles a lot of trivial cases very fast. Can you agree that for this problem, this algorithm's worst case is rather rare? answered 14 Jan '14, 06:07

This can be done with a persistent trie as well , the implementation is quite short as well . answered 19 May '15, 21:35

I have problem in understanding the query part. If we consider the example given in the sample input. Then for the query 1 4 we will get two nodes in the segment tree of interval 13 and 4. Then how we will apply binary search to get the answer. Can anyone tell me. Thankyou. answered 14 Jan '14, 19:04

please someone explain me how this part works: S = 0 while (there is the next number x) { if x <= S + 1: S = S + x else break; } though i have understand nearly why this method works but it would be great if someone explains me how to come up with such an idea to solve this question...... answered 26 Jan '14, 11:35

Answer is hidden because of too many downvotes. Click here to view.
answered 14 Jan '14, 01:37
10
if you wanted to add the most senseless comment in forum, this was a good try...
(14 Jan '14, 01:42)
did he wanted to ask some question ?
(15 Jan '14, 10:03)

Just a small comment about the O(log^2(N)) range sum query over the segment tree. A standard implementation does indeed have this time complexity. But the implementation can be optimized to O(log(N)) per query by using the technique called fractional cascading. This was not necessary for this problem, but someone might be interested in it.