2023年 GESP六级 小杨的握手问题的优雅解法：树状数组实战

ftggdnt

一、问题背景与算法选择

题目要求计算n个人按照特定顺序排队时发生的握手次数，本质上是计算序列中逆序对的数量。树状数组(Fenwick Tree)因其高效的区间查询和单点更新能力(O(logn))成为解决此类问题的理想选择。

二、完整代码实现（带详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. // 树状数组实现类
   
6. class FenwickTree {
   
7. private:
   
8.     vector tree; // 存储树状数组
   
9.     int size; // 数组大小
   
10. public:
    
11.     // 构造函数，初始化大小为n的树状数组
    
12.     FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    
13.     // 更新操作：在index位置增加delta
    
14.     void update(int index, int delta) {
    
15.         // 典型的树状数组更新方式
    
16.         for(; index <= size; index += index & -index)
    
17.             tree[index] += delta;
    
18.     }
    
19. 
    
20.     // 查询操作：求前index个元素的和
    
21.     int query(int index) {
    
22.         int res = 0;
    
23.     // 典型的树状数组查询方式
    
24.         for(; index > 0; index -= index & -index)
    
25.             res += tree[index];
    
26.         return res;
    
27.     }
    
28. };
    
29. int main() {
    
30.     // 优化输入输出
    
31.     ios::sync_with_stdio(false);
    
32.     cin.tie(nullptr);
    
33.     int N;
    
34.     cin >> N;
    
35.     vector<int> order(N);
    
36.     for(int i = 0; i < N; i++) {
    
37.         cin >> order[i];
    
38.         order[i]++; // 转换为1-based索引
    
39.     }
    
40. 
    
41.     // 初始化树状数组
    
42.     FenwickTree ft(N);
    
43.     long long handshakes = 0;
    
44. 
    
45.     // 核心计算逻辑
    
46.     for(int i = 0; i < N; i++) {
    
47.         int current = order[i];
    
48.         // 查询比current小的已存在数的个数
    
49.         handshakes += ft.query(current - 1);
    
50.         // 将当前数加入树状数组
    
51.         ft.update(current, 1);
    
52.     }
    
53. 
    
54.     cout << handshakes << endl;
    
55.     return 0;
    
56. }

复制代码

三、算法核心解析

• 树状数组原理：
  
  
  • 利用二进制索引高效维护前缀和
  • update和query操作的时间复杂度均为O(logn)
  • 空间复杂度O(n)
    
    
• 1-based转换：
  
  
  • 将输入值+1转换为1-based索引
  • 避免处理0索引带来的边界问题
    
    
• 逆序对计算：
  
  
  • 按顺序处理每个人时
  • 查询已处理人中编号比当前小的数量
  • 累加得到总握手次数
    
    

四、复杂度分析与优化

• 时间复杂度：
  
  
  • 预处理：O(n)
  • n次查询和更新：O(nlogn)
  • 总复杂度：O(nlogn)
    
    
• 空间复杂度：
  
  
  • 树状数组：O(n)
  • 输入存储：O(n)
    
    
• 优化方向：
  
  
  • 离散化处理可减少空间使用
  • 并行计算可优化大规模数据
    
    

五、常见问题解答

Q：为什么选择树状数组而不是线段树？ A：树状数组代码更简洁且在解决前缀和问题上效率相当。

Q：1-based转换是否必要？ A：不是绝对必要但能简化代码逻辑，避免处理0索引。

Q：如何处理数值很大的情况？ A：可以通过离散化将大范围数值映射到小范围。

来源：竞赛学习