树状数组（FenwickTree）：区间查询与单点更新数据结构

"树状数组，也称为二进制索引树（Binary Indexed Tree, BIT），是一种高效的数据结构，特别适合处理区间和的查询与更新。这种数据结构可以在O(logN)的时间复杂度内完成单点更新和区间查询，极大地提高了处理大量数据时的效率。 树状数组的基本构造是基于一个数组BIT，其长度通常比原始数组长度多1。初始化时，BIT数组的每个元素初始为0。数组中的每个位置i，BIT[i]表示从位置i开始到数组末尾的区间和。 树状数组的主要操作包括单点更新（Point Update）和区间查询（Range Query）： 1. 单点更新：当我们想要改变数组中的某个位置i的值时，执行update(i, delta)操作。这个操作会递归地将增量delta累加到位置i及其所有祖先节点上，从而影响到从i开始的所有区间和。在Python实现中，`while`循环和位运算（i += i & -i）用于找到需要更新的祖先节点。 2. 区间查询：查询从1到位置i的区间和，使用query(i)函数。这个操作同样采用`while`循环和位运算来累加从i开始的祖先节点的值，返回区间和。Python实现中，`result`变量会累积这些和，并通过i -= i & -i来逐级向上回溯。 树状数组的应用非常广泛，其中包括： - **区间和查询问题**：对于需要频繁查询区间和的问题，如动态维护前缀和，树状数组能提供高效的解决方案。 - **频繁更新的问题**：如果数据集需要不断更新，树状数组可以高效地处理这些更新，同时保持区间查询的性能。 - **逆序对的计算**：在计算数组中的逆序对数量时，树状数组可以辅助实现高效的算法。逆序对是指在有序数组中，较大的元素位于较小元素之前的所有配对。 通过理解和熟练掌握树状数组，开发者可以解决许多与数组和区间操作相关的复杂问题，尤其在大数据处理和算法竞赛中，树状数组是一种强大的工具。"