四叉树--多级分段树

Question

我最近偶然发现了一种名为段树的新数据结构，然后我读到它也可以扩展到二维，但我找不到一个好的来源来了解它的实现细节和其他东西。我想从在编程竞赛中使用它的角度来了解它，而不是在graphics.Some问题领域使用它，使用它也会很有用。有没有人能帮我找个好的资源来读一读？谢谢

Answer 1

将片段树扩展到多个维度，特别是在编程竞赛中，可能会变得非常困难和耗时。

如果您需要多个维度，您应该首先了解二进制索引树，然后尝试将它们扩展到多个维度。

二进制索引树是一种数据结构，在某些情况下，它的性能比段树更好，而在其他情况下，它根本不适合。

在使用分段树时，扩展到多个维度是微不足道的。

在这里您可以找到an article about them。

在这里您可以找到a problem that can help you test your implementation。

Answer 2

有一篇关于1D片段树及其2D泛化的好文章和代码示例。但它是俄语的，所以您可能只需要考虑代码示例=)

http://e-maxx.ru/algo/segment_tree

Answer 3

我不确定你是否会找到更多关于这方面的消息来源。我认为这是留给人们去理解k维段树是如何工作的。站在你的立场，我会试着解决一个可以用它解决的问题。一个简单的例子(我知道这个查询可以用O(1)通过一些预处理完成)：矩形范围和。也就是说:给定一个充满数字的矩阵，回答要求一个子矩阵求和的查询。在这里，您可以使用一棵语义树来拆分高度，然后在每个节点上创建一棵额外的分段树来计算基于宽度的总和。如果你能做到这一点，那么你就知道了关于2-dim的一切。分段树。下一个挑战将是允许更新单个元素-这会变得更难，因为你必须使用一些“艺术”来正确地传播更改(考虑一下段树中的某种类型的缓存)。:)