关于吉老师线段树
  • 板块学术版
  • 楼主hgzxgzx
  • 当前回复18
  • 已保存回复18
  • 发布时间2022/10/7 20:47
  • 上次更新2023/10/27 08:15:13
查看原帖
关于吉老师线段树
545918
hgzxgzx楼主2022/10/7 20:47

吉老师的论文的例题一中的关于时间复杂度的证明我有点看不懂。口胡一下我自己的看法:假设我们已经对整个区间都取了 min\min,这个区间的次大值就没有了,看做负无穷,之后的任何的区间最值操作就和普通线段树区间修改的复杂度一样,所以复杂度 O(n+mlogn)O(n+m\log n) 等于 O(mlogn)O(m\log n)。如有不对,请大家指正。

顺便询问一下有没有这方面的比较好的资料,谢谢了。

2022/10/7 20:47
加载中...