C++中的段树的STL

Question

是否有段树的STL？

在竞争性编程中,需要花费大量时间来编写seg树.我想知道是否有任何STL,以便节省大量时间.

Answer 1

我假设"段树"你实际上是指范围树,它在编程竞赛中比用于存储一组间隔的更专业的结构更常用.

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

在需要总和而不是最小值或最大值的应用程序中,可以使用二进制索引树而不是段树,它更快,占用更少的内存,并且更容易编码(大约十几行或更少).

Answer 2

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