首先你要知道線段樹是怎麼一回事，以及它在這個程式裡是怎麼存的。假設你的線段樹要記錄區間[0,3]裡各個數的個數，那麼這棵樹長這樣：每個結點有一個區間範圍[l,r]，並記錄了在這個範圍內有幾個數。每個結點的兩個孩子的區間範圍是自身的一半。圖中畫出的是樹中有一個0和一個3的情形。樹雖然是樹形結構，但其實可以用陣列來存。上圖中每個結點的index就是這個結點在陣列中的下標。下標為x的結點，其左右孩子的下標分別為2x和2x+1，程式中是寫成位運算形式的。每個結點的範圍[l,r]並沒有儲存，而是在樹中移動時邊走邊算的。你看呼叫每個函式時，後三個引數都是0, n-1, 1，這就是根結點的l, r, index。如果理解了上面這些內容，那麼你只需要知道update和query兩個函式的功能，就可以理解它們的內部實現和外部呼叫了。update(p)的意思是往樹中插入一個數p（即讓p的次數加1）；query(L,R)的意思是求樹中位於區間[L,R]內的數有多少個。這樣，求逆序數的過程，就是對於序列中的每一個數，求出樹中已有的比它大的數有多少個並累加，再把這個數本身插入到樹中去。這就是你畫紅圈的部分在乾的事。紅圈下面的那個迴圈，我也不知道是在幹什麼。
首先你要知道線段樹是怎麼一回事，以及它在這個程式裡是怎麼存的。假設你的線段樹要記錄區間[0,3]裡各個數的個數，那麼這棵樹長這樣：每個結點有一個區間範圍[l,r]，並記錄了在這個範圍內有幾個數。每個結點的兩個孩子的區間範圍是自身的一半。圖中畫出的是樹中有一個0和一個3的情形。樹雖然是樹形結構，但其實可以用陣列來存。上圖中每個結點的index就是這個結點在陣列中的下標。下標為x的結點，其左右孩子的下標分別為2x和2x+1，程式中是寫成位運算形式的。每個結點的範圍[l,r]並沒有儲存，而是在樹中移動時邊走邊算的。你看呼叫每個函式時，後三個引數都是0, n-1, 1，這就是根結點的l, r, index。如果理解了上面這些內容，那麼你只需要知道update和query兩個函式的功能，就可以理解它們的內部實現和外部呼叫了。update(p)的意思是往樹中插入一個數p（即讓p的次數加1）；query(L,R)的意思是求樹中位於區間[L,R]內的數有多少個。這樣，求逆序數的過程，就是對於序列中的每一個數，求出樹中已有的比它大的數有多少個並累加，再把這個數本身插入到樹中去。這就是你畫紅圈的部分在乾的事。紅圈下面的那個迴圈，我也不知道是在幹什麼。