Can you simulate the following process in $O(N.log N)$

Question

Given an array $A[]$ of N integers.

pseudocode:

• Traverse from left to right of this array.
• Let's say you are standing at index $j$.
• For each index i=1 to i=j-1, increment all $A[i]$ by $1$ if and only if $A[i] \ge A[j]$.
• Once done for all $i<j$ move over to the next $j$ ie $j=j+1$

For example lets start with: $7, 5, 2, 1, 8$(1-indexed)

at $j=2 -> 8, 5, 2, 1, 8 (A[1] >= A[2])$

at $j=3 -> 9, 6, 2, 1, 8 (A[1], A[2] >= A[3])$

at $j=4 -> 10, 7, 3, 1, 8 (A[1], A[2], A[3] >= A[4])$

at $j=5 -> 11, 7, 3, 1, 8 (A[1] >= A[5])$

$11, 7, 3, 1, 8$ is the answer

Python code $O(N^2)$. (Note: python list is 0-indexed so printed $j+1$ to match the above 1-indexed example):

A = [7, 5, 2, 1, 8]
N = len(A)

for j in range(1, N):
    for i in range(j):
        if A[i] >= A[j]:
            A[i] += 1
    print("at j = ", j + 1, "->", A)

print("Final answer=", A)

Answer 1

Since the operation "add 1 to all values greater than or equal to i" preserves order, you can augment a self balancing BST with this operation. While the particulars are dependent on how the balancing is done, the idea is to keep in each node how much you need to add to its subtree, and push it to its children when you touch it.

Once you have such a tree, you can maintain all values up to the current index in it, and implement the algorithm in $O(\log n)$ per step.

In pseudocode:

1. Initialize $T$ to be an empty self balancing BST.
2. For $j = 1 \to n$:
   1. Apply to $T$ the operation "add 1 to all values greater than or equal to $A[j]$"
   2. Insert $A[j]$ to $T$, with metadata $j$.
3. For every node $v$ in the tree
   1. Set $A[v.\text{metadata}] = v.\text{value}$
4. Return A