视频字幕
树状数组是一种高效的数据结构，也称为二进制索引树或芬威克树。传统数组在进行区间求和时需要O(n)时间复杂度，而树状数组可以将区间查询和单点更新都优化到O(log n)。它通过巧妙的二进制索引机制，构建了一个树形结构来存储区间信息，大大提高了处理效率。
树状数组的核心是lowbit函数，它通过位运算x与负x来获取二进制数最低位的1。以12为例，12的二进制是1100，负12的二进制表示是11110100，两者进行与运算得到0100，也就是4。这个操作帮助我们确定在树状数组中需要跳跃的步长，是实现高效索引的关键机制。
树状数组的结构基于二进制索引建立。每个节点C[i]存储从i减去lowbit(i)加1到i的区间和。例如C[4]存储A[1]到A[4]的和，C[6]存储A[5]到A[6]的和。通过这种巧妙的存储方式，我们可以用树形结构高效地管理区间信息，不同颜色的节点表示不同的层级关系。
单点更新是树状数组的核心操作之一。当我们要更新位置3的值时，需要更新所有包含位置3的节点。从位置3开始，通过不断加上lowbit值来找到父节点：先更新C[3]，然后是C[4]，最后是C[8]。每次跳跃的步长由lowbit函数决定，整个过程的时间复杂度为O(log n)。
前缀和查询是树状数组的另一个核心操作。要查询前7个元素的和，我们从位置7开始，通过不断减去lowbit值来访问相关节点。首先访问C[7]，然后是C[6]，最后是C[4]。将这些节点的值相加就得到了前7个元素的和。整个查询过程的时间复杂度同样是O(log n)。