AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

【数据结构笔记】动态开点线段树

作者: 作者的头像   Aigrl ,  2022-05-14 14:46:28 ,  所有人可见 ,  阅读 391


0


笔记汇总


在朴素线段树的使用中,有爆值域的风险。

故而产生了动态开点这一解决方式。

结合建图经验,易知用指针可以解决这类问题(树也是一种图)。

线段树每个点只有两个儿子,定义两个指针会更好查找。

但从整体看,并没有降低空间(线段树的点数太大)

所以 动态开点。

实现

结构体的数组大小最好开到上限(因为询问区间导致的最后建点大小不确定)

注意,动态开点线段树结点结构体两指针都不表示区间(指向下方两个点的编号)

但其它值定义方式一样,操作方式一样。

更新时,要先找到其下两个点(不是结点结构体内的指针)

开点操作类似于$Trie$树,有一个动态编号(建了点的数量)。

这也意味着,在任何操作中都必须有一个由上往下开点的步骤(放开头判断)。

当然,已开过的点不用重复开。

0 评论

你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息