四叉树 - 多级分段树

Question

我最近遇到一个叫做分段树的新数据结构，然后读到它也可以扩展到两个维度，但是我找不到一个很好的资源来阅读它的实现细节和其他东西。 我想从在编程竞赛中使用它的角度来了解它，而不是在图形领域。使用它可以解决的一些问题也是有用的。 有人可以请我指出一个很好的来源来阅读它？ 谢谢

Answer 1

我不知道你是否会找到更多的来源。我认为让人们了解k维分割树是如何工作的。在你的位置上，我会尝试解决一个可以用它来完成的问题。简单的例子（我知道这个查询可以通过一些预处理在O（1）中完成）：矩形范围和。即：给定一个填充数字的矩阵，回答询问子矩阵之和的查询。 在这里，您可以使用一棵半树来分割高度，然后在每个节点上为基于宽度的总和创建一个附加分割树。 如果你能做到这一点，那么你知道一切有关2-dim的知识。分段树。 接下来的挑战是允许更新单个元素 - 这会变得更加困难，因为您必须使用一些“艺术”来正确传播更改（考虑段树内的某种类型的缓存）。 :)

Answer 2

有一篇关于一维分段树及其代码示例的二维概括的好文章。但它在俄罗斯，所以你可能不得不把唯一的代码示例=）

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

Answer 3

延伸段树木多个维度，尤其是在程序设计大赛可以变成是非常困难和耗费时间。

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

二元索引树是一种数据结构，在某些情况下，它比段树更好地执行，而在另一些情况下，它仅仅是不合适的。

使用分段树时，对多维的扩展是微不足道的。

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

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