最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 线段树:讲解与模板

    本章内容介绍另一种数据结构—线段树,线段树和前文所提到的前缀和所能解决的问题相似,但使用场景不同

    1 前缀和的局限性

    在使用前缀和时,我们必须保证所生成前缀和的原始数组不能发生元素的更新操作。以一维数组为例,一旦前缀和数组已经生成完毕,此时若改变原始数组中的某个值,那么其后面的前缀和都要发生更改。

     

    可以看出,前缀和方法重新生成前缀和数组的时间复杂度为O(N)

    2 线段树与前缀和的比较

    树是一种比较灵活的数据结构,可以用来解决某个范围内的数据聚合问题,使用线段树,我们可以在O(logN) 的时间里找到数据的聚合信息(如最大值,最小值,总和等),当然,当原始数组发生变更时,更新线段树的时间复杂度也是O(logN)

    数组A[0, 1, … , n-1]的线段树是一颗二叉树,其中每个节点包含数组下标在 [i, j]范围内的聚合信息(如最大值,最小值,总和等),其左右节点分别包含范围 [i, (i+j)/2] , [(i+j)/2+1, j]上的信息

     

     

    在上图所给出的示例中,每个叶节点都是数组{2,4,12,17}的元素 。非叶节点包含范围内相应元素的总和 ,例如(6) 是从索引 0 到索引 1 的元素之和。而根节点 (35) 是它的两个子节点 (6) 和 (29) 的和,也是整个数组的元素之和。

     

     

    线段树与前缀和的区别:

    • 前缀和查询区间的时间复杂度为O(1),   而线段树查询区间的时间复杂度为O(logN),因此,当数组没有修改需求时,前缀和的效率较高。
    • 前缀和修改元素而引起更改的时间复杂度为O(N),而使用线段树修改元素并更改线段树数组的时间复杂度为O(logN),  在面对有修改需求的数组时,线段树可更快完成修改。

    3 线段树的实现

    线段树通常基于数组来实现,由二叉树的性质可知,如果索引为i的元素不是叶节点,那么它的左右节点分别存储在索引2i2i+1处。

     

    以求和操作为例,线段树的操作可以分为以下三部分:

    • 从原始数组生成线段树数组
    • 修改元素时更新线段树数组
    • 使用线段树数组进行区域查询

    3.1 生成线段树

    由线段树的性质可知,如果需要求某个节点p的值,则必须先求出其左右子节点的值,因为节点p的值等于其左右子节点的元素值之和,因此,我们使用自下而上的方法来生成线段树,因此使用后序遍历的方式,递归函数buildTree(root, l, r)的参数含义:

      • root:根元素在tree数组中的索引;
      • l,r:tree元素表示的左右范围。

    时间复杂度:O(N)

    空间复杂度:O(N)

    3.2 更新线段树

    与生成线段树相似,当更新原数组的元素时,总是会修改叶节点的值,然后自下而上更新非叶节点的元素值,以满足非叶节点的元素值等于子节点的元素值之和。递归函数update(root, l, r, key, value)的参数含义:

    • root:根元素在tree数组中的索引;
    • l,r:tree元素表示的左右范围;
    • key, value:要修改的元素下标以及新元素值。

    时间复杂度:O(logN)空间复杂度:O(1)

    3.3 范围查询

    处理步骤与上述操作类似,递归函数query(root, l, r, ql, qr)的参数含义:

    • root:根元素在tree数组中的索引;
    • l,r:tree元素表示的左右范围;
    • ql,qr:要查询范围的左右边界。

    时间复杂度:O(logN)

    空间复杂度:O(1)

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 线段树:讲解与模板

    发表评论

    • 52会员总数(位)
    • 321资源总数(个)
    • 20本周发布(个)
    • 2 今日发布(个)
    • 334稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情