树状数组（Fenwick Tree）原理和优化全面解析

你正在开发一个交易系统，需要实时完成两种操作：

• 更新某个时间点的价格（单点修改）
  
• 快速计算某段时间段内的交易总量（区间查询）
  

当数据量较小时，我们可能会这样实现：

1. vector<int> prices(n);
2. // 单点更新 - O(1)
3. prices[index] += new_value;
4. // 区间查询 - O(n)
5. int sum = accumulate(prices.begin() + l, prices.begin() + r + 1, 0);

复制代码

但当数据量达到百万级时，这样的操作会导致严重的性能瓶颈。尤其当系统要求每秒处理数万次操作时，传统的数组结构显然力不从心。
聪明的开发者可能会想到前缀和优化：
[code]vector prefix(n + 1);// 构建前缀和 - O(n)for(int i = 1; i