把逆序对看成二维偏序，从左到右扫描并用 Fenwick 加速值域桶统计。
OJ: luogu
题目 ID: P1908
难度:普及
标签:二维偏序树状数组离散化逆序对python
日期: 2026-07-16 18:28
形式化题目
给定长度为
思路
先看一个可以直接验证定义的朴素解：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
int n;
int a[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll answer = 0;
// brute.cpp：直接枚举所有下标对，按逆序对定义统计。
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] > a[j]) {
answer++;
}
}
}
cout << answer << '\n';
return 0;
}暴力枚举所有下标对
逆序对为什么是二维偏序？
把每个元素
点 i = (位置 i, 数值 a_i)一个逆序对
i < j 位置维度：i 在 j 左边
a_i > a_j 数值维度：a_i 比 a_j 大也就是说，我们不是只在一条线上比较，而是在两个维度上同时比较。这就是最基础的二维偏序：一维要求“小于”，另一维要求“大于”。
用序列 [5,4,2,6,3,1] 里的前几个点看一下：
下标 i: 1 2 3 4 5 6
数值 a_i: 5 4 2 6 3 1
点: (1,5) (2,4) (3,2) (4,6) (5,3) (6,1)如果当前点是 (5,3)，它能和左边哪些点形成逆序对？需要找左边已经出现过、数值大于 3 的点：
左边点: (1,5) (2,4) (3,2) (4,6)
数值>3: ✓ ✓ × ✓
贡献逆序对: (1,5), (2,5), (4,5) 共 3 个所以扫描到当前位置时，问题变成：前面已经出现的数中，有多少个比当前值大？
桶维护：记录前面出现过的值
最直接的想法是开一个桶 bucket[v]，表示数值排名为 v 的元素在左边出现过几次。扫描到当前排名 rank 时：
比当前值大的数量 = bucket[rank+1] + bucket[rank+2] + ... + bucket[K]这里
bucket[rank]++这张图展示桶的含义：
值排名: 1 2 3 4 5 6
实际值: 1 2 3 4 5 6
bucket: 0 1 0 1 1 1
当前值 rank = 3
要数 rank > 3 的桶：bucket[4] + bucket[5] + bucket[6] = 3桶的想法很直观：每个值排名一个桶，桶里装“左边出现过多少次”。但普通桶的问题是，每次都要把 rank+1..K 扫一遍求和，单次
Fenwick 加速桶：把区间求和压到
Fenwick 树可以理解成“带前缀和加速的桶”。它仍然维护每个排名出现了几次，只是把求和变快了：
普通桶：
bucket[rank]++ 单点加 O(1)
sum(bucket[1..rank]) 前缀和 O(n)
Fenwick：
add(rank, 1) 单点加 O(log n)
prefix_sum(rank) 前缀和 O(log n)扫描到当前值 rank 时，已经看过的元素个数记为 seen：
prefix = 左边 <= 当前值 的数量 = BIT.prefix_sum(rank)
左边 > 当前值 的数量 = seen - prefix相等的元素不能算逆序对，所以查询时用 <= rank 放进 prefix，再用 seen - prefix 得到严格大于当前值的个数。
为什么要离散化？
原值可能达到 bucket[10^9]。但比较大小只关心相对顺序，所以把所有不同的值排序后映射成连续排名：
原值: 1 2 3 4 5 6
排名: 1 2 3 4 5 6
如果原值是: 10 100 1000000000
排名就是: 1 2 3离散化后，Fenwick 的下标就是值的排名。整个过程就是：从左到右扫描位置维度，用 Fenwick 维护值维度的桶，从而统计二维偏序关系。
Python 知识
sorted(set(values))同时完成去重和排序，是离散化的第一步。- 字典推导式把原值映射为从
1开始的排名，作为 Fenwick 下标。 iter(map(int, sys.stdin.buffer.read().split()))适合一次读入大量整数。i & -i是 Fenwick 的lowbit；查询时减去它，修改时加上它。
代码
本文主线解释 Fenwick 做法，对应 Python 代码：
import sys
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
values = [next(data) for _ in range(n)]
rank = {value: i + 1 for i, value in enumerate(sorted(set(values)))}
tree = [0] * (len(rank) + 1)
answer = 0
for seen, value in enumerate(values):
index = rank[value]
prefix = 0
i = index
while i:
prefix += tree[i]
i -= i & -i
answer += seen - prefix
while index < len(tree):
tree[index] += 1
index += index & -index
print(answer)下面是同一思路的 C++ Fenwick 版本：
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-10 21:22
* update_at: 2026-08-10 21:22
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500005;
int n;
int a[MAXN]; // 原序列
int sorted_value[MAXN]; // 排序后的值，用来离散化
int tree[MAXN]; // Fenwick：tree 中维护值排名出现次数
int lowbit(int x) {
return x & -x;
}
void add(int pos, int value) {
for (int i = pos; i <= n; i += lowbit(i)) {
tree[i] += value;
}
}
int prefix_sum(int pos) {
int answer = 0;
for (int i = pos; i > 0; i -= lowbit(i)) {
answer += tree[i];
}
return answer;
}
int get_rank(int value, int value_cnt) {
return (int)(lower_bound(sorted_value + 1, sorted_value + value_cnt + 1, value) - sorted_value);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sorted_value[i] = a[i];
}
sort(sorted_value + 1, sorted_value + n + 1);
int value_cnt = unique(sorted_value + 1, sorted_value + n + 1) - (sorted_value + 1);
ll answer = 0;
int seen = 0; // 已经扫描过的元素个数
for (int i = 1; i <= n; i++) {
int rank = get_rank(a[i], value_cnt);
// prefix 表示左边 <= 当前值的个数。
int prefix = prefix_sum(rank);
answer += (ll)(seen - prefix); // 左边 > 当前值的个数，就是新产生的逆序对数
add(rank, 1); // 当前值加入“值排名桶”
seen++;
}
cout << answer << '\n';
return 0;
}原有 C++ 归并排序版本仍保留在目录中。归并排序也是逆序对的经典解法，但它不是本文“二维偏序 → 桶 → Fenwick”这条主线：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500005;
int n;
int a[MAXN];
int tmp[MAXN];
ll answer;
void merge_sort_count(int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
merge_sort_count(l, mid);
merge_sort_count(mid + 1, r);
int i = l;
int j = mid + 1;
int k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
}
else {
// a[i] > a[j] 时，左半边从 i 到 mid 的所有数都和 a[j] 构成逆序对。
tmp[k++] = a[j++];
answer += (ll)(mid - i + 1);
}
}
while (i <= mid) {
tmp[k++] = a[i++];
}
while (j <= r) {
tmp[k++] = a[j++];
}
for (int p = l; p <= r; p++) {
a[p] = tmp[p];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
answer = 0;
merge_sort_count(1, n);
cout << answer << '\n';
return 0;
}复杂度
离散化需要排序，时间
总结
逆序对是最基础的二维偏序：位置维度要求