# Recover permutation from prefix sums, using segment trees?

I encountered the following problem on Codeforces.

An array of integers $$p_1,p_2,…,p_n$$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $$[3,1,2],[1],[1,2,3,4,5]$$ and $$[4,3,1,2]$$. The following arrays are not permutations: $$[2],[1,1],[2,3,4]$$.

There is a hidden permutation of length $$n$$.

For each index $$i$$, you are given $$s_i$$, which equals to the sum of all $$p_j$$ such that $$j and $$p_j. In other words, $$s_i$$ is the sum of elements before the $$i$$-th element that are smaller than the $$i$$-th element.

How can I solve this problem using segment trees in $$O(n\log n)$$ time?

I tried to understand the solution on Codeforces but I could not understand it. Their solution:

Let us fill the array with numbers from 1 to $$N$$ in increasing order.

1 will lie at the last index $$i$$ such that $$s_i=0$$. Find and remove this index $$i$$ from the array and for all indices greater than $$i$$, reduce their $$s_i$$ values by $$1$$. Repeat this process for numbers $$2,3,\ldots,N$$. In the $$i$$th turn, reduce the elements by $$i$$.

To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $$O(\log n)$$ time in this case. Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

5
0 1 1 1 10

My segment tree will look like:

[1-5](0)
/        \
[1-2](0)      [3-5](1)
/      \         /      \
[1-1](1) [2-2](1)   [3-4](1) [5-5](10)
/       \
[3-3](1)      [4-4](1)

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $$O(n)$$ time.

• @Mike You are right that in a standard segment tree, updating an interval of leaves requires $O(n)$ time: Actually this is already somewhat of an improvement over the naive approach where you call update on each leaf; since a single update takes $O(\log n)$ time (the single leaf change propagates up to the root), then updating all leaves[k] for $i\leq k \leq j$ could take $O(n\log n)$ time. To get to $O(n)$ time, what you are doing is updating all the leaves in sequence, then recomputing the tree from the leaves to the root, and since there are $2N$ nodes, this is $O(n)$ time. – Matthew C Oct 31 '19 at 18:07
• All that is to say, that you can augment your standard segment tree so that the following particular kind of interval update takes $O(\log N)$ time: increment all leaves $k$ in $i\leq k \leq j$ by the same constant $C$. Note this isn't the same as the above discussion, where you could update leaves to their unique new values in total $O(N)$ time; here you really must be calling the same kind of update on all leaves in your interval. Anyway, for instructions on how to augment your segment tree see geeksforgeeks.org/lazy-propagation-in-segment-tree – Matthew C Oct 31 '19 at 18:09
• And you can see in your problem that this is exactly the kind of update you are doing; decrementing ALL leaves to the right of some given node by a constant; "all leaves to the right" is an interval of leaves, and the decrement is by the same amount for each ($-i$, at step $i$ in the solution)) – Matthew C Oct 31 '19 at 18:13

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $$s_i$$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop.

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).

• I think this treads ground that's already familiar to OP. What they need to know is why "update range" can be done in $O(\log n)$ time (and the answer to that is lazy propagation). – Matthew C Dec 1 '19 at 22:05