solution

Cho mảng $a$ có $n$ phần tử. Nghịch thế là cặp $(i, j)$ với $i < j$ và $a_i > a_j$. Hãy đếm tổng số nghịch thế.

Dùng Fenwick Tree (BIT) sau khi nén toạ độ: duyệt từ phải sang trái, với mỗi $a_i$ đếm số phần tử nhỏ hơn đã thấy bằng BIT — tổng thời gian $O(n \log n)$.

Ví dụ $a = [2, 4, 1, 3, 5]$: các cặp $(2,1), (4,1), (4,3)$ → $3$ nghịch thế.