没有合适的资源？快使用搜索试试~ 我知道了~

文库首页行业互联网树状数组(C++版).pdf

树状数组(C++版).pdf

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

0 下载量 174 浏览量 2021-11-09 13:51:54 上传评论收藏 486KB PDF 举报

温馨提示

试读

14页

。。。

资源推荐

资源详情

资源评论

树状数组

第 01 讲什么是树状数组？

树状数组用来求区间元素和，求一次区间元素和的时间效率为 O(logn)。

有些同学会觉得很奇怪。用一个数组 S[i]保存序列 A[]的前 i 个元素和，那么求区间 i,j 的元素和不就为

S[j]-S[i-1]，那么时间效率为 O(1)，岂不是更快？

但是，如果题目的 A[]会改变呢？例如：

我们来定义下列问题：我们有 n 个盒子。可能的操作为

1.向盒子 k 添加石块

2.查询从盒子 i 到盒子 j 总的石块数

自然的解法带有对操作 1 为 O(1)而对操作 2 为 O(n)的时间复杂度。但是用树状数组，对操作 1 和 2 的时间

复杂度都为 O(logn)。

第 02 讲图解树状数组 C[]

现在来说明下树状数组是什么东西？假设序列为 A[1]~A[8]

网络上面都有这个图，但是我将这个图做了 2 点改进。

（1）图中有一棵满二叉树，满二叉树的每一个结点对应 A[]中的一个元素。

（2）C[i]为 A[i]对应的那一列的最高的节点。

现在告诉你：序列 C[]就是树状数组。

那么 C[]如何求得？

C[1]=A[1];

C[2]=A[1]+A[2];

C[3]=A[3];

C[4]=A[1]+A[2]+A[3]+A[4];

C[5]=A[5];

C[6]=A[5]+A[6];

C[7]=A[7];

C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

以上只是枚举了所有的情况，那么推广到一般情况，得到一个 C[i]的抽象定义：

因为 A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把 A[]中的每个元素当成叶子，那么：

C[i]=C[i]的所有叶子的和。

现在不得不引出关于二进制的一个规律：

先仔细看下图：

将十进制化成二进制，然后观察这些二进制数最右边 1 的位置：

1 --> 00000001

2 --> 00000010

3 --> 00000011

4 --> 00000100

5 --> 00000101

6 --> 00000110

7 --> 00000111

8 --> 00001000

1 的位置其实从我画的满二叉树中就可以看出来。但是这与 C[]有什么关系呢？

接下来的这部分内容很重要：

在满二叉树中，

以 1 结尾的那些结点（C[1],C[3],C[5],C[7]），其叶子数有 1 个，所以这些结点 C[i]代表区间范围为 1 的元

素和；

以 10 结尾的那些结点（C[2],C[6]），其叶子数为 2 个，所以这些结点 C[i]代表区间范围为 2 的元素和；

以 100 结尾的那些结点（C[4]），其叶子数为 4 个，所以这些结点 C[i]代表区间范围为 4 的元素和；

以 1000 结尾的那些结点（C[8]），其叶子数为 8 个，所以这些结点 C[i]代表区间范围为 8 的元素和。

扩展到一般情况：

i 的二进制中的从右往左数有连续的 x 个“0”，那么拥有 2^x 个叶子，为序列 A[]中的第 i-2^x+1 到第 i 个

元素的和。

终于，我们得到了一个 C[i]的具体定义：

C[i]=A[i-2^x+1]+„+A[i]，其中 x 为 i 的二进制中的从右往左数有连续“0”的个数。

第 03 讲利用树状数组求前 i 个元素的和 S[i]

理解了 C[i]后，前 i 个元素的和 S[i]就很容易实现。

从 C[i]的定义出发：

C[i]=A[i-2^x+1]+„+A[i]，其中 x 为 i 的二进制中的从右往左数有连续“0”的个数。

我们可以知道：C[i]是肯定包括 A[i]的，那么：

S[i]=C[i]+C[i-2^x]+…

也许上面这个公式太抽象了，因为有省略号，我们拿一个具体的实例来看：

S[7]=C[7]+C[6]+C[4]

因为 C[7]=A[7]，C[6]=A[6]+A[5]，C[4]=A[4]+A[3]+A[2]+A[1]，所以 S[7]=C[7]+C[6]+C[4]

（1）i=7，求得 x=0，那么我们求得了 A[7]；

（2）i=i-2^x=6，求得 x=1，那么求得了 A[6]+A[5]；

（3）i=i-2^x=4，求得 x=2，那么求得了 A[4]+A[3]+A[2]+A[1]。

讲到这里其实有点难度，因为 S[i]的求法，如果要讲清楚，那么得写太多的东西了。所以不理解的同学，

再反复多看几遍。

从（1）（2）（3）这 3 步可以知道，求 S[i]就是一个累加的过程，如果将 2^x 求出来了，那么这个过程用

C++实现就没什么难度。

现在直接告诉你结论：2^x=i&(-i)

证明：设 A’为 A 的二进制反码，i 的二进制表示成 A1B，其中 A 不管，B 为全 0 序列。那么-i=A’0B’

+1。由于 B 为全 0 序列，那么 B’就是全 1 序列，所以-i=A’1B，所以：

i&(-i)= A1B& A’1B=1B，即 2^x 的值。

所以根据（1）（2）（3）的过程我们可以写出如下的函数：

int Sum(int i) //返回前 i 个元素和

{

int s=0;

while(i>0)

{

s+=C[i];

i-=i&(-i);

}

return s;

}

第 04 讲更新 C[]

正如第 01 讲提到的小石块问题，如果数组 A[i]被更新了怎么办？那么如何改动 C[]？

如果改动 C[]也需要 O(n)的时间复杂度，那么树状数组就没有任何优势。所以树状数组在改动 C[]上面的时

间效率为 O(logn)，为什么呢？

因为改动 A[i]只需要改动部分的 C[]。这一点从第 02 讲的图中就可以看出来：

如上图：

假如 A[3]=3，接着 A[3]+=1，那么哪些 C[]需要改变呢？

答案从图中就可以得出： C[3],C[4],C[8]。因为这些值和 A[3]是有联系的，他们用树的关系描述就是：

C[3],C[4],C[8]是 A[3]的祖先。

那么怎么知道那些 C[]需要变化呢？

我们来看“A”这个结点。这个“A”结点非常的重要，因为他体现了一个关系：A 的叶子数为 C[3]的 2

倍。因为“A”的左子树和右子树的叶子数是相同的。因为 2^x 代表的就是叶子数，所以 C[3]的父亲是 A，

剩余13页未读，继续阅读

评论收藏

内容反馈

1.该资源内容由用户上传，如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款（资源遇到问题，请及时私信上传者）

版权申诉

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

苦茶子12138

粉丝: 1w+
资源: 6万+

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

树状数组(C++版).pdf

树状数组简要讲解.pdf

树状数组(C++版).docx

数据结构-树状数组的构建示例(C++实现)

树状数组-C++算法教程（临时保存）

算法NOIP树状数组校门外的树.pdf

ACM巨全模板 .pdf

Visual C++程序开发范例宝典(PDF扫描版).part3

二叉堆、并查集和树状数组.pdf

C++树状数组入门模板和简单应用+二分求逆序对

树状数组另一类用法（C++源码）

Visual C++程序开发范例宝典(PDF扫描版).part2

Visual C++ 程序开发范例宝典光盘源码 （第二版） 3/7

JAVA上百实例源码以及开源项目

JAVA上百实例源码以及开源项目源代码

Cobalt Strike下载

北京邮电大学计算机考研复试笔试资料

计算机系统-笔记-HUN2021级

cs1.6老版本供下载

合成孔径雷达的经典成像算法cs(matlab)仿真代码（吐血整理，内容全，注释全）

港大CS（MSC）面试整理

最新资源

Visual C++ 程序开发范例宝典光盘源码（第二版） 3/7