如何计算多维数组中的反转数？

Question

给定一个1-D数组，比如4个元素5 4 2 3，我知道改进的合并排序（分治）算法可以计算反转数（对，这样我

x1 <= x2,
y1 <= y2,
and A[x2][y2] < A[x1][y1].
Say for N = 2
5 4
2 3

倒置的编号为4对（5,4) (5,2) (5,3)和（4,3）

我不熟悉堆栈溢出。请原谅格式问题。

Answer 1

Fenwick树是非常有用的数据结构，用于维护每个数据元素的频率和操作累积频率数据表。

本教程（BIT）将为您提供数据结构的良好开端。它有所有的实现细节。

理解了数据结构后，您可以使用它来计算数组中的倒置。假设我们有a[1... n]并且倒置被定义为所有对i， j使得i

最初，所有频率都初始化为0。

for i = n to 1
    res += range-sum(1, a[i]-1)
    insert(a[i])

最后，res将是你的答案。

所用时间：O（nlogn）

对于多维，创建多维二进制索引树。以上教程给出了2D-BIT的一个示例

以下是我根据上述教程的实现：

#define sz(x) ((int)x.size())
#define LSOne(x) (x & -x)
typedef long long LL;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

//Use one based indexing
class FenwickTree{
public:
  vvi ft;
  int n;
  FenwickTree(int _n){
    n=_n;
    ft.assign(n,vi(n,0));
  }
  int rsq(int x,int y){
    int sum=0;
    for(;x;x-=LSOne(x))sum += rsqY(x,y);
    return sum;
  }
  int rsqY(int x,int y){
    int sum=0;
    for(;y;y-=LSOne(y))sum += ft[x][y];
    return sum;
  }
  int rsq(int _x,int _y,int x,int y){
    return rsq(x,y)-rsq(x,_y-1)-rsq(_x-1,y)+rsq(_x-1,_y-1);
  }
  void update(int x,int y,int v){
    for(;x<=n;x+=LSOne(x))updateY(x,y,v);
  }
  void updateY(int x,int y,int v){
    for(;y<=n;y+=LSOne(y))ft[x][y] += v; 
  }
  void clear(){
    ft.assign(n,vi(n,0));
  }
};