树状数组 | 维护区间和

1. 树状数组的定义

树状数组（Binary Indexed Tree，简称BIT）是一种数据结构，能够高效地进行前缀和查询和单点更新操作。树状数组常用于解决频繁的区间和查询问题。

2. 树状数组的构建

树状数组使用一个数组BIT[]来维护数据，其中BIT[i]存储从某个位置到当前位置的区间和。构建树状数组的时间复杂度为O(n)。

3. 树状数组的查询

要查询数组中前n项的和，可以通过累加BIT[]中的相关元素来实现。查询操作的时间复杂度为O(log n)。

4. 树状数组的更新

要更新数组中的某一个元素，可以通过更新BIT[]中的相关元素来实现。更新操作的时间复杂度为O(log n)。