I initially solved it in a few lines of code similar to this O(n^2) solution. Now, the only reason why it's O(n^2) is because insertions are O(n). In a few past problems I was able to get around that using Fenwick tree. The idea was simple: maintain a map of indexes, and increment all indexes to the right when inserting. Incrementing lots of things in O(lg n) is exactly what Fenwick tree good for.
Seeing this segment tree solution confirms my hunch even further, because many problems that can be solved with segment tree also can be solved with Fenwick tree and vice versa.
However, I just can't seem to wrap my head around it this time. If we maintain a map of old indexes to new indexes in a Fenwick tree, then we can't just increment “everything to the right” because the order is messed up! If we maintain a backwards map (new indexes to old indexes), then there is no point in incrementing anything at all, because the indexes have to be “shifted”, not incremented.
To illustrate, suppose we have elements
0 1 2 3 4 and we need to reorder them in this way:
- Move 3 to 0.
- Move 2 to 0.
In the end it becomes
2 3 0 1 4. Forward mapping changes in the following way:
0 1 2 3 4 -> 1 2 3 0 4(so far so good, increment
0 1 2at the beginning).
1 2 3 0 4 -> 2 3 0 1 4(here, we need to increment
1 2to the left and
0to the right, no longer one continuous region).
Backwards mapping changes like this:
0 1 2 3 4 -> 3 0 1 2 4(doesn't look good already, shifts instead of increments).
3 0 1 2 4 -> 2 3 0 1 4(ditto).
Am I missing something ridiculously obvious here or is my hunch wrong and Fenwick tree is of no use here?