思路：
先畫(huà)一棵完全二叉樹(shù)， 為節(jié)省空間，采用數(shù)組來(lái)實(shí)現(xiàn)。對(duì)這棵二叉樹(shù)，葉子用于存放數(shù)據(jù)，節(jié)點(diǎn)用于統(tǒng)計(jì)葉子信息。
通過(guò)下面的三種方法，進(jìn)一步節(jié)省空間：
1 節(jié)點(diǎn)只記錄左子樹(shù)葉子信息，右子樹(shù)葉子信息通過(guò)當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)等節(jié)點(diǎn)的值計(jì)算得出。
因而需要指定一個(gè)點(diǎn)，當(dāng)作根節(jié)點(diǎn)的“父節(jié)點(diǎn)”，以便計(jì)算根節(jié)點(diǎn)右子樹(shù)信息。
可以將根節(jié)點(diǎn)從1開(kāi)始編號(hào)，對(duì)節(jié)點(diǎn)i，左孩子編號(hào)為2*i，右孩子編號(hào)為2*i+1，并用編號(hào)0記錄整根樹(shù)所有葉子的信息。
2 對(duì)某些應(yīng)用，葉子信息可以通過(guò)節(jié)點(diǎn)信息計(jì)算得出，因而不保存葉子信息，
3 完全二叉樹(shù)，邊界要求為2^k，為了表示[0, n)這n個(gè)點(diǎn)，需要將n增加到2^k，實(shí)際上，
只要第n個(gè)葉子的父節(jié)點(diǎn)r存在就可以了，編號(hào)大于r的節(jié)點(diǎn)根本不會(huì)被訪(fǎng)問(wèn)到，因而沒(méi)必要分配空間
點(diǎn)樹(shù)的實(shí)現(xiàn)
// 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};
};
//若表示的區(qū)間為[0, M), 則 N >= (M+1+Extra)/2, 其中Extra為大等于m的最小2^t
//完全二叉樹(shù),根節(jié)點(diǎn)為1，對(duì)節(jié)點(diǎn)i，左孩子為2*i，右孩子為2*i+1
//節(jié)點(diǎn)編號(hào)范圍[1, Extra) 葉子編號(hào)范圍[Extra, 2*Extra)， 點(diǎn)n 對(duì)應(yīng) 葉子n+Extra，
//為節(jié)省空間，只記錄各節(jié)點(diǎn)左子樹(shù)下的葉子的個(gè)數(shù)，不記錄葉子出現(xiàn)的個(gè)數(shù)
//info[0] 保存所有葉子的總個(gè)數(shù)， info[i]記錄節(jié)點(diǎn)i的左子樹(shù)下的所有葉子的總個(gè)數(shù)）
template <int M, typename T = int> //區(qū)間[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) //求逆序數(shù)
{
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) //求逆序數(shù) 點(diǎn)樹(shù)實(shí)現(xiàn)
{
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/
本文采用知識(shí)共享署名-非商業(yè)性使用-相同方式共享 2.5 中國(guó)大陸許可協(xié)議進(jìn)行許可，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁(yè)面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利。