保存帖子
发现
索引
热门
陶片放逐
关于
关于线段树查询的时间复杂度
板块
学术版
楼主
K2Cr2O7
当前回复
9
已保存回复
9
发布时间
2020/8/29 21:25
上次更新
2023/11/5 13:59:47
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于线段树查询的时间复杂度
K2Cr2O7
楼主
2020/8/29 21:25
以维护区间和的举例:
查询整个序列
[
1
,
n
]
[1,n]
[
1
,
n
]
,不递归就返回了,所以是
O
(
1
)
O(1)
O
(
1
)
的?
查询单点
[
l
,
l
]
[l,l~]
[
l
,
l
]
,一直要递归到底层,所以是
O
(
l
o
g
n
)
O(logn)
O
(
l
o
g
n
)
的?
所以说线段树是不是查询的区间越大越快?
2020/8/29 21:25
加载中...