c++ - STL 用于 C++ 中的段树

Question

有段树的 STL 吗？

在竞争性编程中，为 seg 树编写代码需要花费大量时间。我想知道是否有任何 STL 可以节省大量时间。

Answer 1

我假设“段树”实际上是指范围树，它在编程竞赛中更常用，而不是用于存储一组间隔的更专业的结构。

C++ 标准库中没有这样的容器，但如果您参加 ACM 比赛，您可以考虑编写自己的容器，并根据需要简单地复制它。你可以在这里找到我自己的实现（包括惰性传播），但如果你在网上搜索，你可能会找到一个更通用的版本。

在需要求和而不是最小值或最大值的应用程序中，您可以使用二叉索引树而不是段树，这样更快、使用更少的内存并且更易于编码（大约十几行或更少）。

Answer 2

C++ 中没有用于段树的 STL。但是，您可以查看名为Interval Container Library (ICL)的 Boost 库，它应该可以满足您的要求。