c++ - C++ 中线段树的 STL

Question

线段树有没有STL？

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

Answer 1

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

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

在需要和而不是最小值或最大值的应用中，可以使用二叉索引树代替线段树，这样速度更快，占用内存更少，也更容易编码(大约十几行或更少)。