通过与 Jira 对比,让您更全面了解 PingCode

  • 首页
  • 需求与产品管理
  • 项目管理
  • 测试与缺陷管理
  • 知识管理
  • 效能度量
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案

25人以下免费

目录

树状数组的原理是什么

树状数组的原理是,树状数组为了节省空间,删去了不必要的结点,将结点数压缩到与数组长度相同。方案是这样的:数组的每个位置代表其在图中垂直向上追溯可以达到的较高的结点。

一、树状数组的原理

原理

树状数组的原理是,树状数组为了节省空间,删去了不必要的结点,将结点数压缩到与数组长度相同。方案是这样的:数组的每个位置代表其在图中垂直向上追溯可以达到的较高的结点。

树状数组可以解决什么问题

可以解决大部分区间上面的修改以及查询的问题,例如1.单点修改,单点查询,2.区间修改,单点查询,3.区间查询,区间修改,换言之,线段树能解决的问题,树状数组大部分也可以,但是并不一定都能解决,因为线段树的扩展性比树状数组要强。

树状数组和线段树的区别在哪

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强,那为什么不直接用线段树呢?问的很好,树状数组的作用就是为了简化线段树,举个例子:一个问题可以用线段树解决写代码半个小时,但是用树状数组只需要10分钟,那么你会选择哪一个算法呢?没错,基于某些简单的问题,我们没必要用到功能性强但实现复杂的线段树(杀鸡焉用宰牛刀)。

优缺点

优点:修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小,并且实现比线段树简单

缺点:扩展性弱,线段树能解决的问题,树状数组不一定能解决。

延伸阅读:

二、完全二叉树

完全二叉树是一种特殊的二叉树,满足以下要求:

  1. 所有叶子节点都出现在 k 或者 k-1 层,而且从 1 到 k-1 层必须达到最大节点数;
  2. 第 k 层可以不是满的,但是第 k 层的所有节点必须集中在最左边。 需要注意的是不要把完全二叉树和“满二叉树”搞混了,完全二叉树不要求所有树都有左右子树,但它要求:
  3. 任何一个节点不能只有左子树没有右子树;
  4. 叶子节点出现在最后一层或者倒数第二层,不能再往上。
相关文章