萌新刚学线段树问关于线段树的储存空间
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复21
  • 已保存回复21
  • 发布时间2024/4/8 21:24
  • 上次更新2024/4/9 13:34:03
查看原帖
萌新刚学线段树问关于线段树的储存空间
745358
ChenZQ楼主2024/4/8 21:24

首先我们一般线段树的存储方式都是u∗2u*2和u∗2+1u*2+1。而这个方式需要4倍空间,但是线段树维护一个长度为n的序列需要 2∗n−12*n-1 的空间,那么如果我们不用上面那种存储方式,而是用一个计数器cnt,每次新开一个点就给他编号为cnt+1并且把cnt++,然后记录父子关系。这种方式是不是就是只需要2倍空间呀。

萌新刚学线段树,问的问题似乎有些若只,求好心大佬解答

2024/4/8 21:24
加载中...