关于线段树查询的时间复杂度
  • 板块学术版
  • 楼主K2Cr2O7
  • 当前回复9
  • 已保存回复9
  • 发布时间2020/8/29 21:25
  • 上次更新2023/11/5 13:59:47
查看原帖
关于线段树查询的时间复杂度
361965
K2Cr2O7楼主2020/8/29 21:25

以维护区间和的举例:

  1. 查询整个序列 [1,n][1,n] ,不递归就返回了,所以是 O(1)O(1) 的?
  2. 查询单点 [l,l ][l,l~] ,一直要递归到底层,所以是 O(logn)O(logn) 的?

所以说线段树是不是查询的区间越大越快?

2020/8/29 21:25
加载中...