高频笔试考点-树状数组（上，前置知识前缀和、差分）

这段时间参加了很多公司的笔试，发现大公司都喜欢考与数据结构相关的知识点。比如：

• 使用 最小堆 来找出最大、最小的N个数
• 使用 贪心+双端队列 来 解决窗口中局部最优问题
• 使用 前缀和数组、差分数组 来统计数组的前缀信息、差分信息
• 树上DP，树上DFS，树状数组等等

本篇博客就主要关注大厂中对于“数组”这个结构的考察点，前缀和、差分、树状数组。前缀和数组 和 差分数组 很简单，至少原理很简单，所以这里就只讲讲前缀和数组 和 差分数组的 具体应用场景。

​ 首先提两个概念，“区间”和“单点”，区间指的是一片范围内的所有数据，单点指的是某个位置的一个数据。我们常见的说法有**“区间查询”，“区间更新”，“单点查询”，“单点更新”**。

1.先谈“区间查询”

​ 还记得“前缀和数组”是用来干嘛的吗？它是为了 快速统计某个区间内所有数据的和。

通过使用前缀和数组维护前缀和信息，我们可以把原始组每次的“区间查询” 转化为前缀和数组 的“单点查询”。

但是可惜的是，如果原数组的数据发生变化的话，比如位于下标的数据需要 +1（发生了“单点更新”），为了继续让前缀和数组维护原数组的前缀信息，我们需要对 这些数据进行更新。遇到“区间更新”的问题，前缀和数组需要维护的代价更高。

2.为了解决数据更新的问题（“区间更新”），我们引入“差分数组”这个数据组织。

​ 差分数组可能有些同学之前没有使用过，所以我按照“差分数组是什么”，“差分数组能干什么”，“怎么使用差分数组”这套流程进行讲解。

与前缀和数组类似，差分数组是为了 维护数组中前后数据的差分信息。

根据差分数组的公式来看，如果nums[i]发生了变更（）,那么diff[i] = diff[i] + , diff[i+1] = diff[i+1] - ，这是“单点更新”。如果[i,j]整个区间内的数据都发生了变更(), 这个差分数组的妙用就出来了，我们更新diff[i] = diff[i] + ，diff[j+1] = diff[j+1] - 就可以了。

​ 了解完前缀和数组和差分数组的原理之后，大家会发现，前缀和数组只适用于“区间查询”，如果存在数据更新，就显得很很乏力。同样的，差分数组适用于“区间更新”，但不适合“单点查询”，更不方便进行“区间查询”。

但是对于实际的应用场景，数据的查询和更新往往是分不开的，所以我们必须掌握在“高效进行区间查询的时候，还可以高效地进行单点更新”，“在高效进行区间更新的时候，还可以高效地进行单点查询”。我们 **树状数组（下）**这篇博客会详细讲解树状数组是如何高效地解决这两个问题的。