简单利用树状数组优化实例

简单利用树状数组优化实例：从 O(n²) 到 O(n log n)

例题链接:左侧严格小于计数_牛客题霸_牛客网

问题简述:

给定一个长度为 n 的数组 a，对于每个位置 i，求前面有多少个数比 a[i] 小。

示例：

输入：a = [5, 2, 4, 1, 3]
输出：0 0 1 0 2
解释：
– i=1, a[1]=5, 前面无数 → 0
– i=2, a[2]=2, 前面[5], 无比2小的 → 0
– i=3, a[3]=4, 前面[5,2], 比4小的有[2] → 1
– i=4, a[4]=1, 前面[5,2,4], 无比1小的 → 0
– i=5, a[5]=3, 前面[5,2,4,1], 比3小的有[2,1] → 2

方法一：暴力解法 O(n²)

核心思路

对于每个位置，遍历前面所有元素，逐个比较统计。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int n;
cin >> n;
vector<int> a(n+1, 0), b(n+1, 0);

for(int i = 1; i <= n; i++) {
cin >> a[i];
int temp = a[i];
// 遍历前面所有元素
for(int j = 1; j < i; j++) {
if(temp > a[j]) // 前面有比当前小的
b[i]++;
}
}

for(int i = 1; i <= n; i++)
cout << b[i] << ' ';
}

复杂度分析

瓶颈：每次查询"前面有多少个比它小"都要遍历一遍，做了大量重复工作。

方法二：树状数组优化 O(n log n)

核心思路

关键观察：我们需要一个数据结构，支持两种操作：

树状数组（Fenwick Tree） 正好满足：单点修改 + 前缀查询都是 O(log n)。

技巧——离散化：如果数值很大（如10⁹），直接开数组会MLE。先将数值映射到 [1, n] 的紧凑范围。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10; // 根据数据范围调整

int n;
int c[N]; // 树状数组

// lowbit: 提取二进制最低位的1
// 例如：6(110) → 2(010), 8(1000) → 8(1000)
int lowbit(int x)
{
return x & (-x);
}

// 在位置x增加v，并更新所有祖先节点
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i))
c[i] += v;
}

// 查询[1, x]的前缀和，即有多少个数 ≤ x
int query(int x)
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i))
res += c[i];
return res;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n;
vector<int> a(n + 1), b(n + 1);
vector<int> all; // 用于离散化

// 读入数据
for (int i = 1; i <= n; i++)
{
cin >> a[i];
all.push_back(a[i]);
}

// 离散化：排序 + 去重
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());

// 逐个处理
for (int i = 1; i <= n; i++)
{
// 找到a[i]在all中的位置（1-based）
int pos = lower_bound(all.begin(), all.end(), a[i]) – all.begin() + 1;

// 查询：前面有多少个数 < a[i]（即离散化值在[1, pos-1]范围内）
b[i] = query(pos – 1);

// 插入：把当前数加入树状数组
add(pos, 1);
}

for (int i = 1; i <= n; i++)
cout << b[i] << ' ';

return 0;
}

两种方法对比

关键步骤图解

以 a = [5, 2, 4] 为例：

离散化：5→3, 2→1, 4→2

树状数组维护的是"每个离散化值出现了几次"

步骤1: 处理5(pos=3)
查询[1,2]的和 = 0 → b[1]=0
在位置3加1 → 数组: [0,0,1,0]

步骤2: 处理2(pos=1)
查询[1,0]的和 = 0 → b[2]=0
在位置1加1 → 数组: [1,0,1,0]

步骤3: 处理4(pos=2)
查询[1,1]的和 = 1 → b[3]=1（前面有2）
在位置2加1 → 数组: [1,1,1,0]

总结

树状数组的核心价值在于将"遍历统计"转化为"前缀和查询"，用 O(log n) 的代数操作替代 O(n) 的线性扫描

结语:

希望本章能够帮助到您~,码字不易,感谢您的点赞收藏o(*￣▽￣*)ブ