树状数组建树时间复杂度证明

树状数组（Binary Indexed Tree, BIT）是一种数据结构，用于快速维护一个数列的前缀和。在树状数组中，每个节点存储的是一段区间内的和。这个区间的范围是根据节点在树状数组中的位置来确定的。

树状数组的建树时间复杂度是 $O(n\log n)$，其中 $n$ 是数列的长度。

证明如下：

首先，我们需要了解树状数组的建树过程。树状数组的建树过程可以分为两个步骤：

1. 初始化数组：将所有节点的值都初始化为0；
2. 更新节点：对于每个数列中的元素，将对应节点的值进行更新。

第一步的时间复杂度是 $O(n)$，因为需要遍历所有节点进行初始化。

第二步的时间复杂度是 $O(n\log n)$，因为每个节点的更新都需要向上遍历树状数组的父节点，并对父节点的值进行更新。因为树状数组的深度为 $\log n$，所以更新每个节点需要的时间复杂度是 $O(\log n)$。总共需要更新 $n$ 个节点，所以总的时间复杂度是 $O(n\log n)$。

综上所述，树状数组的建树时间复杂度是 $O(n\log n)$。