视频字幕
树状数组是一种高效的数据结构,也称为二进制索引树或芬威克树。传统数组在进行区间求和时需要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)。