求解范围最小查询问题
RangeMinQuer的Python项目详细描述
这个数据结构解决了在可比较对象数组的子数组中找到最小值的问题。与原来的问题不同,这个数据结构还支持更新值。
安装
这个包在pypi上提供。只需使用pip install -U RangeMinQuery
来安装它。然后可以使用from RangeMinQuery import SegmentTree
导入它。
用法
初始化
使用SegmentTree()
以comparable和hashable类型中的一组键初始化树。
func=min
指定如何计算任意范围的键的最佳值。default=None
指定每个键的默认值。^ {CD6>}指定每个节点的最大子数。
tree=SegmentTree({1,2,3,4,5},func=min,default=0,maxChildNum=2)
空间复杂度为$O(n)$。
更新
您需要使用update()
来初始化值,或者在必要时通过指定键/值对字典来更新值。目前,还不支持添加新密钥。
tree.update({1:3,4:6})
更新m值,时间复杂度为O(m^ 2)$。
查询
使用query()
查找一系列键的最佳值。范围由元组(a, b)
表示,表示每个键x
,这样a <= x < b
。这里的范围在左侧关闭,在右侧打开,这与python的传统是一致的。
tree.query((1,3))
时间复杂度为$O(log n)$。