algorithm - 给定要拼接的索引数组，生成删除每个元素的顺序

Question

这是一个更大的程序的一部分，但这是瓶颈。
给定一个数字数组，意思是“重复地将这个索引处的元素从数组中拼接出来”，我想生成一个数组，表示每个元素应该拼接的顺序。
所以如下:

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

意味着运行这些操作:

[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

我想生成(没有实际运行上面的所有拼接操作):

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

这是删除每个元素的顺序。
寻找比 O(N^2) 更好的解决方案

以下不是问题的一部分，只是我实际在做什么，对于任何感兴趣的人:
这是接缝雕刻实现的一部分。我正在生成一个压缩格式，表示给定图像中的所有接缝，然后在客户端中删除这些接缝。由于接缝总是在每一步向左或向右移动 1px，因此接缝可以有效地存储为:

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

然后我从图像中移除这个接缝，并计算下一个接缝。存储方面是 2 字节 + 1 位之后每个像素，或者长度为 1024 的接缝存储在 130 字节中。
然而，相对于原始标记，“左 1”和“右 1”仅对第一接缝是准确的。之后，任何接缝都可以跨越另一个接缝，因此相对于原始索引，“右 1”可能意味着向右移动 10，甚至向左移动 10。
换句话说，我只是想解压缩这些数据。

Answer 1

最简单的 O(N log N) 时间实现可能是使用 Fenwick 树。下面的 C++ 实现。

#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';
}