引入

已知一个数列，你需要进行下面两种操作：

将某一个数加上 xx （修改）

求出某区间每一个数的和（查询）

如何解决这个问题呢？

如果直接使用数组来做，那么修改操作复杂度是 \(O(1)\) ,查询复杂度是 \(O(N)\).

而如果使用前缀和数组来做，那么修改操作复杂度是 \(O(N)\) ,查询复杂度是 \(O(1)\).

上面两种方法的总复杂度都是 \(O(N)\)

那么有没有更快的方法呢？有，树状数组便是一种解决方法，它的复杂度是 \(O(logN)\) （在后面我们会说明为什么）

原理

树状数组，是基于二进制的数位的特性的数据结构。所谓的特性指的是什么呢？简单地说就是可以逐位拆解出 \(1\) ,直到整个串被如此表示。

举个例子：给出一个二进制串 \(100101\) ，它可以被分解为 \(100000+100+1\) 。

这样便为求前缀和提供了一条道路：按照拆出来的数分块求前缀和。

比如说要求数组前 \(12\) 个元素的和，利用 \(12_{(10)}=1100_{(2)}=1000_{(2)}+100_{(2)}=8_{(10)}+4_{(10)}\) 。

先求出后 \(4\) 个元素的和（即 \(9-12\) ），再求出除了这 \(4\) 个元素之外后 \(8\) 个元素的和（即 \(1-8\) ）再把它们加起来即可。

这样我们便解决了求前缀和（查询）操作。

讲到这里，我想引入这张图片帮助理解：（我们记 \(x\) 所对应的区间为 c[x]）这张图完美地解释了 \(x\) 能够维护 \(lowbit(x)\) 个元素（ \(lowbit(x)\) 指 \(x\) 在二进制下最后一个 \(1\) 以及它后面所有的 \(0\) 构成的二进制串所对应的数，比如说 \(lowbit(6)=lowbit(110_{(2)})=10_{(2)}=2\) ）

下面来讲讲更新操作：

核心问题便是：一个数改变了，需要改变什么相关的区间？

答案是：改变维护的区间包括这个数的区间，还是举例来说，如果 a[9] 改变了，由上图可以看出，c[9],c[10],c[12]（ \(12\) 之后的不考虑）均要改变。事实上，c[x]上面的区间是c[x+lowbit(x)] （比如 \(9_{(10)}=1001_{(2)}\) 于是 \(9\) 上面一层区间便是\(1001_{(2)}+lowbit(1001_{(2)})=1010_{(2)}=10_{(10)})\) 依次类推）。

这样我们便知道如何更新了。

代码实现

//修改 p指的是当前位置，k指的是加上k（如果tree[p]=k则是修改为k）void modify(int p,int k){    for(;p<=n;p+=lowbit(p)) tree[p]+=k;}//查询int query(int p){    int res=0;    for(;p;p-=lowbit(p)) res+=tree[p];    return res;}

复杂度分析

结合代码，复杂度分析可以更便于理解：

以查询为例，复杂度无疑取决于那个for循环会执行多少次。根据lowbit的定义，

即使p所对应的二进制串都是 \(1\),也不过是循环 \(1\) 的个数次。

具体地说，\(N=111...111_{(2)}\)（有 \(x\) 个 \(1\) ），而 \(N\) 可以近似看成是 \(2^x\) ,故循环的次数为 \(x=logN\),

故对应的复杂度是 \(O(logN)\) 。

类似的，修改的操作亦然。

上一篇：有依赖的背包问题

下一篇：vim插件配置

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

引入

原理

代码实现

复杂度分析

发表评论

最新留言

关于作者

推荐文章