何时使用段树以及何时使用BIT

Question

我没有一个场景。但对于我们必须只使用的一般情况

1. 在某个范围内更新（例如清除某个范围i-j中的所有值）
2. 查询某个范围中的某个值。（示例RMQ）
3. 对单个元素进行更新（第1点的具体情况）
4. 搜索范围中的特定值（再次是点2的特定情况）

所有这些操作都可以用BIT或段树来执行。但除了3和2的一些特定情况外，分段树的效率要高得多。（Infact BIT对RMQ等查询没有任何帮助）

BIT最明显的优点是它更容易编码。

Answer 1

（以下是我花了几周时间处理段树和BIT问题后的想法，所以我对它很陌生）

BIT更容易编码，但在某些情况下，您可以很容易地将其可视化并关联到段树。BIT提供的另一个优点是占用较小的空间（O（n）空间）。

根据我的感觉，与BIT相比，分段树更容易理解，因此您可以很容易地将其应用于给定的情况并将其关联起来。在分段树中，懒惰传播也更简单易懂。因此，分段树可以有效地在一个范围内进行更新。