关于节点个数
查看原帖
关于节点个数
151589
_⁢ 楼主2023/1/26 18:32

分析朴素实现的时间复杂度:

  • 单次线段树区间操作涉及到 log2n+O(1)\log_2 n+O(1) 个节点。
  • 分叉要 ×2\times 2
  • 比较两个数下放标记有 22 的常数。
  • 区间赋值有 22 的常数。(区间)
  • 单点修改有 11 的常数。
  • 找全 11 区间有 11 的常数。(有疑问)

而且由于会增广 2m2m 次,一共需要开 2×2(2+2+1+1)mlog2n=24mlog2n2\times 2(2+2+1+1)m\log_2 n=24m\log_2 n 个节点。(但是好像也卡不满)

不知道分析的是否准确(

2023/1/26 18:32
加载中...