樹狀數組應用之——求逆序對

這裡說的很好，把求逆序的步驟說的很明白，我也是看完才懂的，之前自己想了很久就是不明白為什麼可以用樹狀數組求逆序

　　

轉載：

樹狀數組，具體的說是 離散化+樹狀數組。這也是學習樹狀數組的第一題.

算法的大體流程就是：

1.先對輸入的數組離散化，使得各個元素比較接近，而不是離散的，

2.接着，運用樹狀數組的标準操作來累計數組的逆序數。

算法詳細解釋：

1.解釋為什麼要有離散的這麼一個過程？

    剛開始以為999.999.999這麼一個數字，對于int存儲類型來說是足夠了。

    還有隻有500000個數字，何必要離散化呢？

    剛開始一直想不通，後來明白了，後面在運用樹狀數組操作的時候，

    用到的樹狀數組C[i]是建立在一個有點像位存儲的數組的基礎之上的，

    不是單純的建立在輸入數組之上。

    比如輸入一個9 1 0 5 4，那麼C[i]樹狀數組的建立是在，

    下标 0 1 2 3 4 5 6 7 8 9

    數組 1 1 0 0 1 1 0 0 0 1

    現在由于999999999這個數字相對于500000這個數字來說是很大的，

    是以如果用數組位存儲的話，那麼需要999999999的空間來存儲輸入的資料。

    這樣是很浪費空間的，題目也是不允許的，是以這裡想通過離散化操作，

    使得離散化的結果可以更加的密集。

2. 怎麼對這個輸入的數組進行離散操作？

   離散化是一種常用的技巧，有時資料範圍太大，可以用來放縮到我們能處理的範圍；

   因為其中需排序的數的範圍0---999 999 999；顯然數組不肯能這麼大；

   而N的最大範圍是500 000；故給出的數一定可以與1.。。。N建立一個一一映射；

   ①當然用map可以建立，效率可能低點；

   ②這裡用一個結構體

   struct Node

   {

      int v,ord;

   }p[510000];和一個數組a[510000];

   其中v就是原輸入的值，ord是下标；然後對結構體按v從小到大排序；

   此時，v和結構體的下标就是一個一一對應關系，而且滿足原來的大小關系；

   for(i=1;i<=N;i++) a[p[i].ord]=i;

   然後a數組就存儲了原來所有的大小資訊；

   比如 9 1 0 5 4 ------- 離散後aa數組就是 5 2 1 4 3；

   具體的過程可以自己用筆寫寫就好了。

3. 離散之後，怎麼使用離散後的結果數組來進行樹狀數組操作，計算出逆序數？

    如果資料不是很大， 可以一個個插入到樹狀數組中，

    每插入一個數， 統計比他小的數的個數，

    對應的逆序為 i- getsum( aa[i] ),

    其中 i 為目前已經插入的數的個數，

    getsum( aa[i] ）為比 aa[i] 小的數的個數,

    i- sum( aa[i] ) 即比 aa[i] 大的個數， 即逆序的個數

    但如果資料比較大，就必須采用離散化方法

    假設輸入的數組是9 1 0 5 4， 離散後的結果aa[] = {5,2,1,4,3};

在離散結果中間結果的基礎上，那麼其計算逆序數的過程是這麼一個過程。

1，輸入5，   調用upDate(5, 1),把第5位設定為1

1 2 3 4 5

0 0 0 0 1

計算1-5上比5小的數字存在麼？ 這裡用到了樹狀數組的getSum（5） = 1操作，

現在用輸入的下标1 - getSum(5) = 0 就可以得到對于5的逆序數為0。

2. 輸入2， 調用upDate(2, 1),把第2位設定為1

1 2 3 4 5

0 1 0 0 1

計算1-2上比2小的數字存在麼？ 這裡用到了樹狀數組的getSum（2） = 1操作，

現在用輸入的下标2 - getSum(2) = 1 就可以得到對于2的逆序數為1。

3. 輸入1， 調用upDate(1, 1),把第1位設定為1

1 2 3 4 5

1 1 0 0 1

計算1-1上比1小的數字存在麼？ 這裡用到了樹狀數組的getSum（1） = 1操作，

現在用輸入的下标 3 - getSum(1) = 2 就可以得到對于1的逆序數為2。

4. 輸入4， 調用upDate(4, 1),把第5位設定為1

1 2 3 4 5

1 1 0 1 1

計算1-4上比4小的數字存在麼？ 這裡用到了樹狀數組的getSum（4） = 3操作，

現在用輸入的下标4 - getSum(4) = 1 就可以得到對于4的逆序數為1。

5. 輸入3， 調用upDate(3, 1),把第3位設定為1

1 2 3 4 5

1 1 1 1 1

計算1-3上比3小的數字存在麼？ 這裡用到了樹狀數組的getSum（3） = 3操作，

現在用輸入的下标5 - getSum(3) = 2 就可以得到對于3的逆序數為2。

6. 0+1+2+1+2 = 6 這就是最後的逆序數

分析一下時間複雜度，首先用到快速排序，時間複雜度為O(NlogN),

後面是循環插入每一個數字，每次插入一個數字，分别調用一次upData()和getSum()

外循環N, upData()和getSum()時間O(logN) => 時間複雜度還是O(NlogN).

最後總的還是O(NlogN).