李超树与凸壳技巧，应该在什么情况下优先选择哪一个？

Question

我很难理解凸包技巧，相比之下，李超树更容易理解。但是，理解凸包技巧是否重要呢？

- Chaos

Answer 1

首先，您应该仔细查看数据结构 LiChao Tree (LC) 和 Convex Hull Trick (CHT) 支持的操作。它们都解决相同的基本问题 - 我们有一组直线(线性函数)S和以下操作：

1. 向集合中添加一条直线/线性函数
2. 对于给定的X坐标，在位置X处找到最大值的函数/线性函数。

现在，您应该学习哪一个呢？我也认为LC更容易理解（而且实现起来也更短）。但是，LC有一个CHT没有的限制 - LC只能回答整数坐标X类型的查询2。此外，因为它非常类似于线段树，所以我们不能支持X坐标必须位于任意大区间内的查询。使用CHT，您对线的坐标和X的查询值没有限制。

在竞争性编程环境中（我猜这就是问题的来源），在许多问题中，LiChao树足够使用，但是使用CHT更加灵活多样，可能有一些问题不能仅通过LC来解决。

- thefunkyjunky