带范围更新的多维段树。
segment-tree的Python项目详细描述
具有范围操作的段树
这是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以运行测试。