李朝树VS凸壳招数.应该首选哪个以及何时首选?

Question

我很难理解凸包技巧。李朝树更容易理解。了解凸包技巧也很重要吗？

Answer 1

首先，您应该仔细查看两个数据结构 LiChao Tree (LC) 和凸包技巧 (CHT) 支持哪些操作。它们都解决了相同的基本问题 - 我们有一组线(线性函数)S 和运算：

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

现在，你应该学习哪一个？我还发现LC更容易理解(而且实现起来也更短)。但是，LC 有一个 CHT 没有的限制 - LC 可以回答类型 2 的查询。仅适用于整数坐标 X，并且由于它与段树非常相似，因此我们无法支持 X 坐标必须位于的任意大间隔。使用 CHT，您对线的坐标和 X 的查询值没有限制。

在竞争性编程的背景下(我想这就是问题的来源)，LiChao树在许多问题上都足够了，但是CHT更通用，并且可能存在一些仅用LC无法解决的问题。