Given an array of indicies to splice, generate the order in which each element was removed

Question

This is part of a larger program, but this is the bottleneck.

Given an array of numbers that mean "repeatedly splice the element at this index out of an array", I want to generate an array that represents the order in which each element should be spliced.

So the following:

[3, 1, 4, 4, 3, 1, 1]

means to run these operations:

[a, b, c, d, e, f, g]
[a, b, d, e, f, g]    // 3rd element removed, c
[b, d, e, f, g]       // 1st element removed, a
[b, d, e, g]          // 4th element removed, f
[b, d, e]             // 4th element removed, g
[b, d]                // 3rd element removed, e
[d]                   // 1st element removed, b
[]                    // 1st element removed, d

And I want to generate (without actually running all of the splice operations above):

[2, 6, 1, 7, 5, 3, 4]

which is the order in which each element was removed.

Looking for a solution better than O(N^2)

---

Below is not part of the question, just what I'm actually doing, for anyone interested:

This is part of a seam carving implementation. I'm generating a compressed format that represents all of the seams in a given image, and then removing those seams in the client. Since a seam always moves 1px left or right at each step, a seam can efficiently be stored as:

starting index, left, right, left, left, left, right, ...

I then remove this seam from the image, and calculate the next one. Storage wise it's 2 bytes + 1 bit per pixel after that, or a seam of length 1024 is stored in 130 bytes.

With respect to the original indicies, however, "left 1" and "right 1" is only accurate for the first seam. After that any seam can cross over another seam, so "right 1", with respect to the original indicies, could mean move right 10, or even move left 10.

In other words I'm just trying to decompress this data.

Answer 1

The simplest O(N log N)-time implementation would probably be with a Fenwick tree. C++ implementation below.

#include <iostream>
#include <vector>

int NextPowerOfTwo(int n) {
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  return n + 1;
}

class FenwickTree {
 public:
  explicit FenwickTree(const int n) : sums_(NextPowerOfTwo(n)) {}

  void Add(int index, const int delta) {
    while (index < sums_.size()) {
      sums_[index] += delta;
      index += index & -index;
    }
  }

  int RankQuery(int target) const {
    int index = 0;
    for (int stride = sums_.size() >> 1; stride > 0; stride >>= 1) {
      if (sums_[index + stride] < target) {
        target -= sums_[index + stride];
        index += stride;
      }
    }
    return index + 1;
  }

 private:
  std::vector<int> sums_;
};

std::vector<int> Decompress(const std::vector<int>& splice_indices) {
  const int n = splice_indices.size();
  FenwickTree tree(n);
  for (int i = 1; i <= n; i++) tree.Add(i, 1);
  std::vector<int> result(n);
  for (int i = 1; i <= n; i++) {
    const int j = tree.RankQuery(splice_indices[i - 1]);
    tree.Add(j, -1);
    result[j - 1] = i;
  }
  return result;
}

int main() {
  for (int i : Decompress({3, 1, 4, 4, 3, 1, 1})) std::cout << ' ' << i;
  std::cout << '\n';
}