立即注册
查看: 666|回复: 6

面试必考的算法与数据结构详解(内含习题练习)

已绑定手机
发表于 2021-5-6 19:54:18 | 显示全部楼层 |阅读模式 来自 广东省深圳市
树状数组,经典树形数据结构之一,代码很短,但其蕴含的算法思想却非常精妙。可以这么说,刷算法题却不懂树状数组,那绝对算是一大遗憾。
树状数组,常用于高效处理「一个数组的更新以及前缀和的求取」。具体来说,其常用于高效求解如下问题:
给定一个长度为 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))。对比之前的做法,树状数组的解法在时间复杂度上有根本性的优势,而这也正是我们学习该算法的原因。

树状数组
树状数组加快运算的关键,在于对二进制的进一步挖掘,因此我们首先来回忆一下二进制。
以正整数 29 为例,其二进制为 11101,因此 29 可以根据其二进制进一步表示为:
1.jpg


完整内容请下载附件查看
游客,如果您要查看本帖隐藏内容请回复


发表于 2021-5-7 16:58:13 | 显示全部楼层 来自 广东省深圳市南山区
1111111111111
发表于 2021-5-18 12:35:01 | 显示全部楼层 来自 湖北省武汉市
11111111111111111
已绑定手机
发表于 2022-2-24 15:46:57 | 显示全部楼层 来自 上海市浦东新区
学习一下
发表于 2022-3-17 00:15:26 | 显示全部楼层 来自 台湾省新北市
感謝分享
已绑定手机
发表于 2024-2-6 11:16:48 | 显示全部楼层 来自 四川省
11111111111111111
已绑定手机
发表于 2024-3-20 09:32:04 | 显示全部楼层 来自 广东省深圳市
22222222222222222
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

合作/建议

TEL: 19168984579

工作时间:
周一到周五 9:00-11:30 13:30-19:30
  • 扫一扫关注公众号
  • 扫一扫打开小程序
Copyright © 2013-2024 一牛网 版权所有 All Rights Reserved. 帮助中心|隐私声明|联系我们|手机版|粤ICP备13053961号|营业执照|EDI证
在本版发帖搜索
扫一扫添加微信客服
QQ客服返回顶部
快速回复 返回顶部 返回列表