algorithm - 给定数组和键，求其左右子数组中小于或等于自身的元素个数？

Question

我必须找到小于或等于 i 的元素数量- 左右子数组中数组的第 th 个元素。

例如如果我的数组是

A[]=4 3 5 2 2 5

我的 2 个数组将是

0 0 2 0 0 5

和

3 2 3 1 1 0

i第一个数组的第 - 个元素表示小于或等于 i 的元素数i 左侧的第 - 个元素-th 元素。

i第二个数组的第 - 个元素表示小于或等于 i 的元素数i 右边的第 - 个元素-th 元素。

我可以使用两个循环在 O(n²) 中找到这些数组。

这可以在 O(n) 内完成吗？

Answer 1

您可以使用 Fenwick Tree 在 O(nlogm) 中执行此操作(其中 n 是 A 的长度，m 是数组中最大元素的大小) .

Fenwick 树(也称为二叉索引树)允许您将元素添加到数组并在 O(logn) 时间内计算连续元素的总和。有教程不错on topcoder .

在这个问题中，我们可以使用 Fenwick 树来存储我们看到每个值的次数的直方图。直方图一开始是空的，然后我们逐渐向直方图中插入元素。

所以我们需要遍历数组，每次先计算有多少元素的值小于当前值，然后将当前值添加到数组。

Python代码:

def find_lower(A):
    """Return B where B[i] is the number of elements <= A[i] in A[0:i]"""
    top = max(A) + 1
    F = fenwick_new(top)
    left = []
    for a in A:
        left.append( fenwick_sum(F,a) )
        fenwick_increase(F,a,1)
    return left

A=[4, 3, 5, 2, 2, 5]
print find_lower(A)
print find_lower(A[::-1])[::-1]

这使用了一些标准的 Fenwick 树函数:

def fenwick_new(m):
    """Create empty fenwick tree with space for elements in range 0..m"""
    # tree[i] is sum of elements with indexes i&(i+1)..i inclusive
    return [0] * (m+1)

def fenwick_increase(tree,i,delta):
    """Increase value of i-th element in tree by delta"""
    while i < len(tree):
        tree[i] += delta
        i |= i + 1

def fenwick_sum(tree,i):
    """Return sum of elements 0..i inclusive in tree"""
    s = 0
    while i >= 0:
        s += tree[i]
        i &= i + 1
        i -= 1
    return s