An array is built starting with an empty array, and then a sequence of insertions:
- insert $a_1$ at index $z_1=1$
- insert $a_2$ at index $z_2$
- insert $a_3$ at index $z_3$
- ...
and so on. When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence $(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.
My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions; but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.
Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:
- the element which ends up at index 1 was the last one which arrived with index 1.
- the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
- the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.
... and so on. However I can't think of the algorithms or data structures that would make this information useful.
Update: There are two $O(n\log n)$ solutions below: the first one, which I accepted, that uses an AVL tree, and one which I learned of afterward that uses a semgent tree, and is somewhat simpler.