### PROBLEM LINK:

**Author:** Constantine Sokol

**Tester:** Mahbub

**Editorialist:** Jingbo Shang

### 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:

```
S = 0
while (there is the next number x) {
if x <= S + 1:
S = S + x
else
break;
}
the forbidden sum is S + 1.
```

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):

```
S = 0
while (true) {
newS = the sum of {x | x <= S + 1}
if (S == newS):
break
S = newS
}
the forbidden sum is S + 1.
```

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**. 0-th is an empty tree, **i**-th 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 **R**-th tree and **(L-1)**-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.

Tester’s solution can be found here.