思路：

    先畫一棵完全二叉樹， 為節省空間，采用數組來實現。對這棵二叉樹，葉子用于存放數據，節點用于統計葉子信息。

通過下面的三種方法，進一步節省空間：

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 中國大陸許可協議進行許可，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。