可替代Fenwick Tree的简易高效数据结构有哪些？

Fenwick树（二叉索引树）确实能在数组动态变化时高效维护前缀和，更新和查询操作的时间复杂度都是O(logN)，结构也紧凑，但实现起来总得多查资料或者费脑子抠细节——我在实际开发和Stack Overflow答题里也很少用它，一般会找性能相近但实现更简单的替代方案。

针对你提出的需求，推荐静态简化线段树作为替代，完全符合各项要求：

核心设计思路 #

用一个大小为2*next_power_of_two(N)的数组构建线段树（若N不是2的幂，取大于等于N的最小2的幂作为线段树的叶子节点总数）。叶子节点对应原数组的元素，内部节点存储对应区间的元素和。

1. 初始化（O(N)时间与空间） #

• 计算最小的size，满足size >= N且size是2的幂
• 创建长度为2*size的数组sums，初始值全为0
• 原数组的第i个元素（0<=i<N）对应线段树的size + i位置

2. update(i, x, y)操作（O(logN)时间，无内存分配） #

• 计算值的变化量：delta = y - x
• 从叶子节点位置pos = size + i开始，向上遍历每个父节点，将sums[pos] += delta，直到遍历到根节点（pos=1）
• 全程仅在初始化的数组上修改，无额外内存分配

3. query(i)操作（O(logN)时间） #

• 查询前i个元素的和，等价于计算原数组区间[0, i-1]的和（当i=0时返回0）
• 初始化结果res = 0，左指针l = size，右指针r = size + i - 1
• 当l <= r时循环执行：
  • 若l是奇数，将sums[l]加到res，并将l += 1
  • 若r是偶数，将sums[r]加到res，并将r -= 1
  • 将l和r都除以2（向下取整），移动到父节点层级
• 最终返回res

这个实现比Fenwick树直观很多，不需要记忆复杂的位运算规则，逻辑清晰易懂，而且完全满足你提出的时间、空间及操作要求。即使N不是2的幂，只需要将多余的叶子节点保持初始0值即可，不会影响计算结果。

内容的提问来源于stack exchange，提问作者Matt Timmermans