面试必考的算法与数据结构详解.docx

树状数组，经典树形数据结构之一，代码很短，但其蕴含的算法思想却非常精妙。可以这么说，刷算法题却不懂树状数组，那绝对算是一大遗憾。 树状数组，常用于高效处理「一个数组的更新以及前缀和的求取」。具体来说，其常用于高效求解如下问题： 给定一个长度为 n 的数组 nums，需要支持两类操作： 操作 1: 将 nums 的数值增加 v 操作 2: 求取 nums[1] + nums[2] + ... + nums 的值 对于上述问题，如果我们采用直接的做法，则操作 1 的时间复杂度为 O(1)，操作 2 的时间复杂度为 O(n)。假如一共有 q 次操作，则总的时间复杂度为 O(qn)。 而如果使用树状数组来求解，则操作 1 和操作 2 的时间复杂度均为 O(log(n))。假如一共有 q 次操作，则总的时间复杂度为 O(qlog(n))。对比之前的做法，树状数组的解法在时间复杂度上有根本性的优势，而这也正是我们学习该算法的原因。 树状数组 树状数组加快运算的关键，在于对二进制的进一步挖掘，因此我们首先来回忆一下二进制。