algorithm - 李超树VS凸壳绝招。应该首选哪个以及何时？

Question

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

Answer 1

首先，你应该仔细看看LiChao Tree (LC) 和Convex Hull Trick (CHT) 这两个数据结构支持什么操作。它们都解决了相同的基本问题——我们有一组线(线性函数)S 和操作:

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

现在，您应该学习哪一个？我还发现 LC 更容易理解(而且实现起来也更短)。然而，LC 有一个 CHT 没有的限制 - LC 可以回答类型 2 的查询。仅对于整数坐标 X，而且，由于它非常类似于线段树，我们不能支持任意大的区间，其中 X 坐标必须说谎。使用 CHT，您对线的坐标和 X 的查询值没有任何限制。

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