树状数组求逆序对

i=0, 处理数值x=3
  sum(3) = 0          (小于等于3的已有0个)
  已插入总数 i = 0    (因为还没插)
  前面比3大的个数 = i - sum(3) = 0 - 0 = 0
  答案 += 0
  add(3, 1)           // 插入一个3

i=1, 处理数值x=1
  sum(1) = 0          (小于等于1的已有0个)
  已插入总数 i = 1    (前面已经插了一个3)
  前面比1大的个数 = 1 - 0 = 1  (就是那个3)
  答案 += 1 → 答案=1
  add(1, 1)           // 插入一个1

i=2, 处理数值x=2
  sum(2) = ?          // 已经插入了3和1，所以小于等于2的有1（一个1），所以 sum(2)=1
  已插入总数 i = 2
  前面比2大的个数 = 2 - 1 = 1  (是那个3)
  答案 += 1 → 答案=2
  add(2, 1)           // 插入一个2

初始： tree[1]=0, tree[2]=0, tree[3]=0  (下标1..3)

第1个元素 x=3：
  sum(3) = tree[3] = 0
  前面比3大的 = 0 - 0 = 0
  答案=0
  add(3,1):
    idx=3 → tree[3] +=1 → tree[3]=1
    idx=3+lowbit(3)=3+1=4 > n 结束
  现在树状数组: [0,0,0,1]  (下标0不用，1..3: tree[1]=0, tree[2]=0, tree[3]=1)

第2个元素 x=1：
  sum(1) = tree[1] = 0
  已插入数 i=1
  前面比1大的 = 1 - 0 = 1
  答案=1
  add(1,1):
    idx=1 → tree[1] +=1 → tree[1]=1
    idx=1+lowbit(1)=1+1=2 → tree[2] +=1 → tree[2]=1
    idx=2+lowbit(2)=2+2=4>n 结束
  现在树状数组: tree[1]=1, tree[2]=1, tree[3]=1

第3个元素 x=2：
  sum(2) = tree[2] = 1 (因为tree[2]代表区间[1..2]的和)
  已插入数 i=2
  前面比2大的 = 2 - 1 = 1
  答案=2
  add(2,1):
    idx=2 → tree[2] +=1 → tree[2]=2
    idx=2+lowbit(2)=2+2=4>n 结束
  最终树状数组: tree[1]=1, tree[2]=2, tree[3]=1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Fenwick {
private:
    int n;                      // 树状数组的大小
    vector<int> tree;           // 存储树状数组
    int lowbit(int x) { return x & -x; }
public:
    Fenwick(int n) : n(n), tree(n + 1, 0) {}

    // 在位置 idx 上增加 delta
    void add(int idx, int delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += lowbit(idx);
        }
    }

    // 查询前缀和 [1..idx]
    int sum(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= lowbit(idx);
        }
        return res;
    }
};

// 主函数：计算逆序对数目
long long count_inversions(vector<int>& a) {
    int n = a.size();

    // 1. 离散化
    vector<int> sorted = a;              // 复制原数组
    sort(sorted.begin(), sorted.end());  // 排序
    // 去重（如果数值可能重复）
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

    // 将每个原数值映射为从1开始的排名
    vector<int> rank(n);
    for (int i = 0; i < n; ++i) {
        // lower_bound 找到第一个 >= a[i] 的位置，下标从0开始，+1后从1开始
        rank[i] = lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin() + 1;
    }

    // 2. 初始化树状数组，大小为不同数值的个数
    Fenwick ft(sorted.size());
    long long ans = 0;                   // 逆序对总数

    // 3. 从左到右扫描
    for (int i = 0; i < n; ++i) {
        int x = rank[i];                 // 当前元素的离散化值
        int less_or_equal = ft.sum(x);  // 前面已有元素中 <= x 的个数
        int greater = i - less_or_equal;  // 前面比 x 大的个数（i 是已插入的总数）
        ans += greater;                  // 累加逆序对
        ft.add(x, 1);                    // 将当前元素插入树状数组
    }

    return ans;
}

int main() {
    vector<int> arr1 = {3, 1, 2};
    cout << "逆序对个数: " << count_inversions(arr1) << endl; // 2

    vector<int> arr2 = {5, 2, 6, 1};
    // 5,2,6,1 逆序对: (5,2),(5,1),(2,1),(6,1) 共4个
    cout << "逆序对个数: " << count_inversions(arr2) << endl; // 4

    vector<int> arr3 = {1, 2, 3, 4, 5};
    cout << "逆序对个数: " << count_inversions(arr3) << endl; // 0

    return 0;
}

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 下标从1开始

    def lowbit(self, x):
        return x & -x

    def add(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += self.lowbit(idx)

    def sum(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= self.lowbit(idx)
        return res

def count_inversions(arr):
    # 1. 离散化
    sorted_vals = sorted(set(arr))  # 排序并去重
    # 建立原值到排名的映射（从1开始）
    val_to_rank = {val: i+1 for i, val in enumerate(sorted_vals)}

    n = len(arr)
    ft = Fenwick(len(sorted_vals))
    ans = 0

    # 2. 从左到右扫描
    for i, val in enumerate(arr):
        x = val_to_rank[val]
        less_or_equal = ft.sum(x)   # 前面 <= x 的元素个数
        greater = i - less_or_equal  # 前面大于 x 的元素个数（i是已插入的总数）
        ans += greater
        ft.add(x, 1)                # 插入当前元素

    return ans

# 测试
if __name__ == "__main__":
    print(count_inversions([3, 1, 2]))      # 2
    print(count_inversions([5, 2, 6, 1]))   # 4
    print(count_inversions([1, 2, 3, 4, 5])) # 0