Grove

Grove 是一个段树库，它允许在数据段上执行通用用户定义的查询和操作，并配对不同的平衡二叉树（splay 树、avl 树等）。Grove 可以表示大多数类型的增强二叉树，只需实现几个特质。

在 Grove 中，段树是一个包含一系列值的结构，它可以回答关于值连续段的问题，以及/或者对连续段中的所有值执行操作。

例如，一个标准的整数段树可能在对数时间内计算段中值的总和，段的最高值，以及向段中的所有值添加一个常数。

为什么选择 Grove

尽管平衡二叉树的实现非常丰富，但大多数实现仅实现了一种 Set 或 Map 有序值的类型。几乎所有实现仅实现了一种特定的平衡树，具有特定的值类型，除了大小和索引数据之外没有其他类型的摘要数据，当然也没有段操作类型。此外，几乎没有实现暴露足够的实现细节，以便用户在需要时实现自己的树算法。

目前，如果您想找到 BTreeSet 中的第 i 个元素，您需要从头开始重新实现数据结构或修改现有代码。如果您想有一个高效的 union 方法，那很不幸。

尽管所有这些都可以以通用方式实现，但用户只需实现几个特质就能获得所需的数据结构。

目标

Grove 旨在成为最通用的段树库。Grove 应该能够表示尽可能多的段树/增强树类型（并且它肯定比作者所知的任何其他实现都要多）。Grove 在以下方面是通用的

• 平衡树算法（目前仅实现 splay 树、avl 树和 Treap）。
• 值类型。
• 您可以在结构中搜索元素的方式。
• 段摘要 - 存储在每个节点中的子树的增强数据。
• 段操作 - 可以高效应用于整个段的操作，通过延迟推送实现。

此外，Grove旨在能够实现用户自己的树算法。然而，这可能需要更多的工作。

缺点

自然地，由于代码将被通用编写，一些常见的优化可能无法实现。它可能不是每个特定实例都尽可能高效的。即使Rust的单态化保证了代码会针对你的特定实例进行优化。

此外，该库可能太大且复杂，包含大量特性和抽象。我尽最大努力在所有地方提供良好的文档。然而，这是编写高度通用代码的代价。

现有技术

已经有一些实现是有些通用的。据作者所知，它们可以总结为

• 许多Set和Map类型是在有序值类型上通用的。
• Haskell的FingerTree实现允许用户提供摘要数据，并基于该数据实现通用二分搜索。

基本用法

Data特质

Data特质是一个标记特质，指定可以执行哪些查询和操作。您可以使用从example_data提供的预制的实例，例如PlainData<V>或SizeData<V>。或者，您也可以创建自己的组合。该Data特质有三个关联类型

• Data::Value是树中表示的值的类型。
• Data::Summary是查询特定段时的结果。
• Data::Action是可以在树的段上执行的操作的类型。如果您不想为您的树提供摘要或操作，请使用example_data::Unit代替。

这些类型必须实现该特质并遵守其限制，以便树可以正确地表现。请参阅其文档。

选择这三个类型后，您可以使用(Value, Summary, Action)作为实现Data特质的类型，或者创建您自己的新标记特质以实现Data特质。

use grove::*;
use example_data::{Size, Unit};

/// instantiation for an int set type
type IntSetData = (
    /* ordered integers */ i32,
    /* for indexing purposes */ Size,
    /* no actions */ Unit
);

type Set = treap::Treap<IntSetData>;

树操作

总的来说，您可以在对数时间内执行这些操作

• 插入、删除和修改特定值。
• 计算段的Data::Summary类型摘要值。
• 对段的每个元素应用Data::Action类型操作。
• 选择要查询/应用操作的段，或使用二分搜索搜索特定元素。请参阅locators模块。
• 反转树的段（作为Action类型的一部分）。
• 分割和连接段树。

这些树操作可以在trees模块中的相应特质中找到。此外，大多数操作都可以使用Slice类型访问，例如tree.slice(locator).insert(new_value)。

为了使用某种类型的树，例如红黑树、AVL树、伸展树、treaps、scapegoat树、常规不平衡树或任何其他树，用户必须在trees模块中实现特质的树类型。（目前实现了splay/AVL/treaps/不平衡树）

use grove::*;
use locators::ByKey; // for ordered sets
use example_data::{Size, Unit};

/// instantiation for an int set type
type IntSetData = (
    /* integers */ i32,
    /* for indexing purposes */ Size,
    /* no actions */ Unit
);

type Set = treap::Treap<IntSetData>;

let mut my_set: Set = [0,1,2,4,6,7,8].iter().cloned().collect();
// At the location in the ordered set where 5 should be, insert 5
my_set.slice(ByKey((&5,))).insert(5).unwrap();
// Delete the element at index 2 and ensure it is 2
assert_eq!(my_set.slice(2).delete().unwrap(), 2);
let vec: Vec<i32> = my_set.into_iter().collect();
assert_eq!(vec, vec![0,1,4,5,6,7,8]);

高级示例

在库中的示例文件夹（该文件夹会自动从crates.io中删除），有两个示例展示了在两个数据结构/算法问题中使用库的方法。一个是yarra gnisrever，项目欧拉的第680题。另一个是pyramid base，来自IOI 2008的问题。

这两个问题展示了如何为特定的使用场景定义自己的Data实例。它们还展示了如何编写与树类型通用的代码：它们都使用相同的代码在treaps、splay树和avl树上运行。

注意：要运行pyramid_base，您需要从这里下载pyramid base测试文件，并将它们保存到名为"pyramid_base_test_files"的新文件夹中。请参阅示例代码。