data-structures - 计算 i 左侧小于 A[i] 的值的高效程序

Question

有人可以提供 NlogN 复杂高效的程序来计算 i 左侧小于 A[i] 的值吗？

我知道如何在 n 方中做事。如果可能的话提供链接。

Answer 1

我想到的一种方法是反转数组 O(n)，你的问题减少到找到出现在 A[i] 右侧的小于 A[i] 的元素数量，它使用 BST 并取 O (nlogn) 存储每个节点的子节点数。

这个链接也很有用。

Answer 2

使用索引树。基本上你遍历数组并更新索引 A[i] 处的索引树。对于每个数字，答案是您到达它时索引树中它之前的总和。这种方法的问题是它需要大量的内存。如果您的数字可能非常大（或非常小），您可能需要压缩它们。这是C++代码：

#include<iostream>
using namespace std;
const int MAX_N=1024; //maximum number of numbers
const int MAX_VAL=1023; //maximum value that the numbers take
const int MIN_VAL=-1024; //minimum value that the numbers take
int arr[MAX_N];
int indTree[MAX_VAL-MIN_VAL+1];
int ans[MAX_N];
int n;
void update(int ind, int val) //standard index tree function that updates the value at index ind
{
    while (ind<=MAX_VAL-MIN_VAL+1)
    {
        indTree[ind-1]+=val;
        ind+=ind&-ind;
    }
}
int sum(int ind) //standard index tree function that calculates the sum of element before ind
{
    int sum=0;
    while (ind>0)
    {
        sum+=indTree[ind-1];
        ind-=ind&-ind;
    }
    return sum;
}
void makePositive() //makes all numbers positive
{
    for (int i=0;i<n;++i)
    {
        arr[i]=arr[i]-MIN_VAL+1;
    }
}
void solve()
{
    makePositive();
    for (int i=0;i<n;++i)
    {
        //ans[i]=sum(arr[i]); choose one of the two
        ans[i]=sum(arr[i]-1); //the first one calculates the number of numbers smaller or equal to the current
        //and the second one calculates the number of numbers strictly smaller than the current
        update(arr[i],1);
    }
}
void input()
{
    cin>>n;
    for (int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
}
void output()
{
    for (int i=0;i<n;++i)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    input();
    solve();
    output();
    return 0;
}

编辑：算法的性能是 O(N log(M))，其中 M 是数字的范围。空间复杂度为 O(M)。您可以通过压缩数字来改善这一点，这会降低 M。这样做不会提高性能，因为压缩函数的性能是 O(N log(M))，但最坏情况下的空间复杂度将是 O( N），因为它是不同数字的数量，在最坏的情况下，它们都不同，不同数字的数量是 N。这是使用一种可能的压缩函数的代码：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int MAX_N=1024; //maximum number of numbers
int arr[MAX_N];
int arr2[MAX_N];
int indTree[MAX_N];
int ans[MAX_N];
int n;
map<int, int> newNum;
void update(int ind, int val) //standard index tree function that updates the value at index ind
{
    while (ind<=MAX_N)
    {
        indTree[ind-1]+=val;
        ind+=ind&-ind;
    }
}
int sum(int ind) //standard index tree function that calculates the sum of element before ind
{
    int sum=0;
    while (ind>0)
    {
        sum+=indTree[ind-1];
        ind-=ind&-ind;
    }
    return sum;
}
void compress() //compresses the numbers
{
    int currNum=1;
    for (int i=0;i<n;++i)
    {
        arr2[i]=arr[i];
    }
    sort(arr2,arr2+n);
    for (int i=0;i<n;++i)
    {
        if (newNum[arr2[i]]==0)
        {
            newNum[arr2[i]]=currNum;
            ++currNum;
        }
    }
    for (int i=0;i<n;++i)
    {
        arr[i]=newNum[arr[i]];
    }
}
void solve()
{
    compress();
    for (int i=0;i<n;++i)
    {
        //ans[i]=sum(arr[i]); choose one of the two
        ans[i]=sum(arr[i]-1); //the first one calculates the number of numbers smaller or equal to the current
        //and the second one calculates the number of numbers strictly smaller than the current
        update(arr[i],1);
    }
}
void input()
{
    cin>>n;
    for (int i=0;i<n;++i)
    {
        cin>>arr[i];
    }
}
void output()
{
    for (int i=0;i<n;++i)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
int main()
{
    input();
    solve();
    output();
    return 0;
}