雁过无痕

思路：

    先画一棵完全二叉树， 为节省空间，采用数组来实现。对这棵二叉树，叶子用于存放数据，节点用于统计叶子信息。

通过下面的三种方法，进一步节省空间：

1   节点只记录左子树叶子信息，右子树叶子信息通过当前节点和父节点等节点的值计算得出。

     因而需要指定一个点，当作根节点的“父节点”，以便计算根节点右子树信息。

     可以将根节点从1开始编号，对节点i，左孩子编号为2*i，右孩子编号为2*i+1，并用编号0记录整根树所有叶子的信息。

2   对某些应用，叶子信息可以通过节点信息计算得出，因而不保存叶子信息，

3   完全二叉树，边界要求为2^k，为了表示[0, n)这n个点，需要将n增加到2^k，实际上，

    只要第n个叶子的父节点r存在就可以了，编号大于r的节点根本不会被访问到，因而没必要分配空间

点树的实现
// www.cnblogs.com/flyinghearts
#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
 
template<int N> struct Round2k {
  enum { down = Round2k<N / 2u>::down * 2, 
         up = down == N ? down : 2 * down };
}; 

template<> struct Round2k<1> {
  enum { down = 1, up = 1};
};
 
//若表示的区间为[0, M), 则 N >= (M+1+Extra)/2, 其中Extra为大等于m的最小2^t
//完全二叉树,根节点为1，对节点i，左孩子为2*i，右孩子为2*i+1
//节点编号范围[1, Extra)  叶子编号范围[Extra, 2*Extra)， 点n 对应 叶子n+Extra，
//为节省空间，只记录各节点左子树下的叶子的个数，不记录叶子出现的个数
//info[0] 保存所有叶子的总个数， info[i]记录节点i的左子树下的所有叶子的总个数）

template <int  M, typename T = int>  //区间[0, M)
class  PointTree {
  enum { Extra = Round2k<M>::up, N = (M + 1 + Extra) / 2u }; 
  // T data[M]; 
  T info[N];
  
public:
  PointTree() { clear(); }
  void clear() { memset(this, 0, sizeof(*this));}
  int size() { return info[0]; }
  int capacity() { return N; }
  
  void add(int n) {
    ++info[0];
    for (int  i = Extra + n; i > 1; i /= 2u) 
      if (i % 2u == 0)  ++info[i / 2u]; 
  }
  
  void erease(int  n) { 
    --info[0];
    for (int i = Extra + n; i > 1; i /= 2u)
      if (i % 2u == 0)  --info[i / 2u]; 
  }
  
  void erease_safe(int n) { if (count(n)) return erease(n); }
  
  int count(int n) {
    // int sum = 0, i = Extra + n;
    // while (i % 2u)  sum += info[(i /= 2u)];
    // return info[i / 2u] - sum;
    int i = Extra + n;
    if (i % 2u == 0) return info[i / 2u];
    int sum = 0;
    do { i /= 2u; sum += info[i]; } while (i % 2u);
    return info[i / 2u] - sum;
  }
  
  int lt(int  n) {
    int sum = 0 ;
    for (int i = Extra + n; i > 1; i /= 2u ) 
      if (i % 2u) sum += info[i / 2u];
    return sum;
  }
  
  int lteq(int  n) {
    //if (n == N - 1) return info[0]; 
    if (N == Extra && n == N - 1) return info[0];
    return lt(n + 1); 
  }
    
  int gt(int  n)  { return info[0] - lteq(n); }
  int gteq(int  n) { return info[0] - lt(n); }
  
  int operator[](int n) { //第n+1小 
    int i = 1;
    while (i < Extra) {
      if (n < info[i]) { i *= 2; }
      else { n -= info[i]; i = i * 2 + 1; }  
    }
    return i - Extra;    
  }
  
}; 


int ra(int arr[], int len) //求逆序数
{
  int sum = 0;
  for (int i = 0; i < len - 1; ++i)
    for (int j = i + 1; j < len; ++j)
      if (arr[i] > arr[j]) ++sum;
  return sum;    
}

template<int N>
int rb(int arr[], int len) //求逆序数 点树实现
{
  PointTree<N> pt;
  int sum = 0;
  for (int i = 0; i < len; ++i) {
    pt.add(arr[i]);
    sum += pt.gt(arr[i]);
  }
  return sum;  
}

int main()
{
  const int N = 6;
  int arr[N] = { 4, 3,2,1,0,5};
  printf("%d \n", ra(arr, N));
  printf("%d \n", rb<N>(arr, N));
  
}

作者： flyinghearts
出处： http://www.cnblogs.com/flyinghearts/
本文采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。