简介

这是区间树数据结构的一种变体，包含两种此类结构 - 区间-点树和点-区间树。区间-点树允许插入区间和查询点，而点-区间树允许插入点和查询区间。所有操作都在 O(log(树的大小)) 复杂度下运行。树可以通过您想要支持的操作进行参数化，您可以使用它们来解决如下问题

• 某些点的区间总和是多少？
• 某些点的区间乘积是多少？
• 某些区间的点总和是多少？
• 某些区间中最大的点是哪个？
• 某些区间中最小的点是哪个？

请注意，这允许解决“在线”版本的问题，即可以混合修改区间集和查询。

用法

请参阅 examples/ 目录中的示例。

命名

我不确定这个数据结构的正确名称是什么 - 我在我的算法课程中学习了这个波兰语名称“drzewo przedziałowe”，可以翻译成“区间树”。然而，它似乎与标准的区间树实现略有不同 - 而不是存储所有区间，我只在节点中保留相关数据。（尽管，技术上，这可以是一组包含此节点的所有区间）。