典型线段树特性对比

树种 单点修改 单点查询 区间修改 区间和查询 区间最值查询
线段树(点修改) O(Log(N)) O(1) 不支持 O(Log(N)) O(Log(N))
线段树(区间修改) O(Log(N)) O(Log(N)) O(Log(N)) O(Log(N)) O(Log(N))
张昆玮线段树 O(1) O(1) 未实现 O(Log(N)),常数小 未实现
张昆玮线段树(差分) O(Log(N)) 借助区间最值查询,O(Log(N)) 未实现 未实现 O(Log(N))

最后更新: 2020年1月9日