PURQ问题
给定一个数组,我们希望在其上能高效地进行(1)区间范围查询:sum(L,R);(2)单点更新:update(position,new_value)。这样的问题称为点更新区间查找(Point Update Range Query)问题。选择一个好的数据结构是高效解决问题的先决条件,对于这种比较简单的问题采用树状数组效果贼棒。
两种极端数据结构
我们用表示一次查询用时O(f(n)),一次更新用时O(g(n))
方法
我们直接用原来的数组即可,更新每次查询 [L,R] 范围和只需累积原数组相应位置即可,最差情形需要遍历整个数组耗时O(n)
方法
我们创建一个和数组,每个位置表示原数组从第一个位置累加到此位置的和。此时查询[L,R] 范围和使用积分思想用区间两端点的和相减即可,只需要O(1)时间。但此时更新数组耗时就很长了,最差情形(例如更新第1个位置)需要对和数组的每个元素进行重新计算,耗时O(n)。
注意如果数组是 immutable 的,此种方法为最优解。
方法——树状数组
前面两种方法分别走向了方便更新数组和方便查询的极端,我们需要进行 tradeoff。
Insight
和数组的方法对从1开始所有可能的部分和进行了求和,这带来查询方便的同时也带来了更新的困难。更新的困难度与和包含的元素个数成正比。如果我们对数组进行合理划分然后只保存一部分和,这样在大大方便更新数组的同时也保留了快速查询和的特性。
lowbit
在说明树状数组前,我们先引入lowbit概念:lowbit 表示一个数从二进制最低位开始计数第一个 1 位所代表的值。易得lowbit = x & (~x + 1)。类比补码显然位与第二部分表示是的是 x 的相反数,所以代码可以表示这样写:
树状数组
树状数组(也称为Binary Indexed Tree (BIT)、Fenwick tree),就是一种只保存部分和的数组,其每个位置 i 保存区间(i-lowbit(i),i]和的数组(左开右闭)。如下图所示,每个位置只保存其右下部分的和。注意其为 1-index 的,因为 0-index 对 lowbit 支持灰常不友好,所以我们下标 0 位置不存 value。
如果我们把其“向左拉”成一颗堆状二叉树,那么由一个节点向根部走下标变化为 i + lowbit(i),向左子叶走则变为 i - lowbit(i)。(这个是接下来算法核心部分,可以算几个理解一下)。
对于更新操作来讲,如果更新一个位置,我们只需要更新该位置相关的祖先节点即可。
对于查询操作可以分解为两部分,从 1 开始查询到 right 位置的和,这个只要计算 right 位置到叶子节点路径上的和即可。而从 left 位置到 right 位置的和可以看做从 1 开始查询到 right 位置的和减去从 1 开始查询到 left - 1 位置的和。
复杂度
由于无论是查询还是更改每次循环操作都可以看做是二进制表示中 1 的个数的减少或增加,其次数最多不会超过其二进制表示的位数——log(n)。
总结与展望
本文主要介绍了用于解决PURQ问题一种优美数据结构——树状数组。对于RURQ(Range Update Range Query)问题,其实也可以用这种数据结构来做,不过我们还是等后面线段树(segment tree)来讲解吧。
领取专属 10元无门槛券
私享最新 技术干货