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

fiwhgikbl

一、问题背景与算法选择

题目要求计算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：可以通过离散化将大范围数值映射到小范围。

来源：竞赛学习