segment-tree

此包包含各种数据结构，可用于快速在某些数组中执行区间查询或修改。

此包中的数据结构都是树。树使用数组表示，以实现高性能和低内存使用。尽管包名为线段树，但此包中并非所有树都是线段树。

Cargo.toml

[dependencies]
segment-tree = "2"

示例

以下示例显示了一个线段树，它允许以对数时间查询任何区间。

use segment_tree::SegmentPoint;
use segment_tree::ops::Min;

let array = vec![4, 3, 2, 1, 2, 3, 4];
let mut tree = SegmentPoint::build(array, Min);

// Compute the minimum of the whole array.
assert_eq!(tree.query(0, tree.len()), 1);

// Compute the minimum of part of the array.
assert_eq!(tree.query(0, 3), 2);

// Change the 1 into a 10.
tree.modify(3, 10);

// The minimum of the whole array is now 2.
assert_eq!(tree.query(0, tree.len()), 2);

此包还有一个 PointSegment 类型，它允许修改区间。

相关的包 prefix_sum 也可能很有趣。