将排列转换为反转表示

Question

第一个N自然数的置换P = [a1, a2, ... , aN]可以由逆I = [i1, i2, ... , iN]的列表表示，其中iK告诉我们在置换P中，在K之前可以找到多少大于K的数。

示例：如果P = [3, 1, 4, 2]，则I = [1, 2, 0, 0]（3放在1之前，3和4放在2之前，而3和4之前没有任何较大的数字）。

有一种明显的算法可以将排列从标准形式转换为反转形式，并在O(N^2)中运行（我们只需遵循定义和计数）。逆变换也是如此（稍微不那么直接）。

有没有一种算法的时间复杂度更低？

Answer 1

有一个简单的迭代动态编程算法可以解决这个问题：对于从1到n（排列长度）的所有i，取数字i，看看i的P中剩下多少元素已经被看到。由于我们按递增顺序处理i，我们知道看到的元素而不是是大于i-的元素，因此我们计算并记下这些元素的数量。诀窍是引入一个外部列表来跟踪P中的哪些元素已经被看到。

首先，让我们看看如何用O(n^2)的方式来实现它。例如，如果P=[4, 3, 2, 1]，则算法将执行如下：

1. 创建一个初始化为零的结构tree。如果迭代算法已经看到P中第j个位置的元素，则它在位置j中保持"1"。

2. 取1，确定pos==3。在tree[pos]中写下"1"。计算等于0的num_seen=sum(tree[0:3])。在I[0]处写下pos - num_seen + 1。之后：tree = [0, 0, 0, 1], I = [3, 0, 0, 0]

3. 取2，在树[1]上写下"1"，在I[1]处写下1。CCD_ 29。

4. 取3，在树[2]中写下"1"，在I[2]处写下0。CCD_ 30。

5. 取4，在树[0]中写下"1"，在I[3]处写下0。tree = [1, 1, 1, 1], I=[3,1,0,0]。

第二个技巧是使用有效的数据结构来计数在CCD_ 32时间内看到的元素的数量，而不是如上所述的CCD_ 33。

以下是Python代码，它使用Fenwick树来快速计算可见元素的数量：

def ft_sum(tree, a, b):
  if a == 0:
      s = 0;
      while  b >= 0:
          s += tree[b];
          b = (b & (b + 1)) - 1
      return s
  return ft_sum(tree, 0, b) - ft_sum(tree, 0, a - 1)
def ft_adjust(tree, k, v):
    while k < len(tree):
        tree[k] += v
        k |= k + 1
def calcI(P):
    n = len(P)
    tree = [0] * n
    I = [0] * n
    positions = [0] * n
    for i in xrange(n):
        positions[P[i]-1] = i
    tree = [0] * n
    for i in xrange(n):
        pos = positions[i]
        ft_adjust(tree, pos, 1)
        num_seen = ft_sum(tree, 0, pos)
        I[i] = pos - num_seen + 1
    return I

Answer 2

同时，我找到了一个简单的解决方案，关于伪代码，它也可以在O(n log n)中工作。

initialize AVL-tree T
initialize array I of length n
for i = 1, 2, ... , n:
    I[P[i]] = T.countGreaterThan(P[i])
    T.add(P[i])