李超树VS凸壳绝招。应该首选哪个以及何时？
Li Chao tree vs Convex hull trick. Which should be preferred and when?
我很难理解凸包技巧。李超树更容易理解。了解凸包技巧也很重要吗？
首先，你应该仔细看看LiChao Tree（LC）和Convex Hull Trick（CHT）这两个数据结构支持什么操作。它们都解决了相同的基本问题——我们有一组线（线性函数）S 和操作：
- 向集合中添加一个 line/linear 函数
- 对于给定的X坐标，求函数在X位置的最大值。
现在，你应该学哪一个？我还发现 LC 更容易理解（而且实施起来也更短）。然而，LC 有一个 CHT 没有的限制 - LC 可以回答类型 2 的查询。仅对于整数坐标 X，而且，由于它非常类似于线段树，我们不能支持任意大的区间，其中 X 坐标必须说谎。使用 CHT，您对线的坐标和 X 的查询值没有限制。
在竞争性编程的背景下（我想这就是问题的来源）LiChao 树足以解决许多问题，但是 CHT 更通用，并且可能存在一些仅用 LC 无法解决的问题。
我很难理解凸包技巧。李超树更容易理解。了解凸包技巧也很重要吗？
首先，你应该仔细看看LiChao Tree（LC）和Convex Hull Trick（CHT）这两个数据结构支持什么操作。它们都解决了相同的基本问题——我们有一组线（线性函数）S 和操作：
- 向集合中添加一个 line/linear 函数
- 对于给定的X坐标，求函数在X位置的最大值。
现在，你应该学哪一个？我还发现 LC 更容易理解（而且实施起来也更短）。然而，LC 有一个 CHT 没有的限制 - LC 可以回答类型 2 的查询。仅对于整数坐标 X，而且，由于它非常类似于线段树，我们不能支持任意大的区间，其中 X 坐标必须说谎。使用 CHT，您对线的坐标和 X 的查询值没有限制。
在竞争性编程的背景下（我想这就是问题的来源）LiChao 树足以解决许多问题，但是 CHT 更通用，并且可能存在一些仅用 LC 无法解决的问题。