什么是树状数组？

树状数组（Binary Indexed Tree 或 Fenwick Tree）是一种精巧的数据结构，它可以在对数时间内完成数组的单点更新和前缀和查询。对于需要频繁更新和查询累积和的场景，它比普通数组（查询 O(n)）和前缀和数组（更新 O(n)）更高效。

核心思想

树状数组的核心思想是利用二进制的特性来管理一个“树状”的结构。数组 C 中的每个元素 C[i] 存储了原始数组 A 中一个特定区间的和。这个区间的长度由 i 的二进制表示中最低位的 1（lowbit）决定。