segment-tree 0.3.2

具有范围操作的段树

这是python 3段树的一般实现。

• o（logn）时间内的半群距离运算
• 内置支持max，min，sum操作
• 可扩展以支持更多的半群操作
• 对多维树的支持有限
• 当前不支持python 2

安装

pip3 install segment-tree

段树（一维）

fromsegment_treeimport*array=[3,1,5,3,13,7,2,7,2]tree=SegmentTree(array)t.query(1,3,"sum")# 9t.update(0,10)# [10, 1, 5, 3, 13, 7, 2, 7, 2]t.query(0,8,"min")# 0t.update(2,-1)# [10, 1, -1, 3, 13, 7, 2, 0, 2]t.query(0,2,"min")# -1

fromsegment_treeimport*array=[1,2,3,4,5]t=SegmentTree(array)t.update_range(0,2,6)# 6 6 6 4 5t.update_range(1,4,2)# 6 2 2 2 2t.query(0,3,"min")# 2

多维段树（alpha版本，可能有错误）

基本用法

fromsegment_treeimport*a=[[[1,2],[1,3]],[[-1,-2],[-1,-3]]]tree=MultidimensionalSegmentTree(a)tree.query([(0,1),(0,0),(0,0)],max)# 1tree.query([(1,1),(0,1),(0,1)],sum)# -7tree.query([(0,1),(1,1),(0,1)],min)# -3

测试

执行python3 setup.py test以运行测试。