我最近遇到了一种称为段树的新数据结构，然后读到它也可以扩展到二维，但我找不到一个好的来源来阅读它的实现细节和其他内容。我想从在编程竞赛中使用它的角度来了解它，而不是在图形领域。使用它可以解决的一些问题也很有用。有人可以指点我一个很好的来源来阅读它吗？谢谢
问问题
844 次
3 回答
2
将段树扩展到多个维度，尤其是在编程竞赛中可能会变得非常困难且耗时。
如果你需要多维度，你应该首先了解二叉索引树，然后尝试将它们扩展到多维度。
二叉索引树是一种数据结构，在某些情况下，它比分段树表现更好，而在其他情况下，它根本不适合。
使用分段树时，对多个维度的扩展是微不足道的。
在这里你可以找到一篇关于它们的文章。
在这里您可以找到一个可以帮助您测试您的实现的问题。
于 2013-02-10T15:20:04.383 回答
1
有一篇关于 1D 线段树及其代码示例的 2D 泛化的好文章。但它是俄语的，所以你可能只需要考虑代码示例 =)
于 2013-02-09T19:34:14.550 回答
0
我不确定您是否会找到更多有关此的资源。我认为人们需要了解 k 维线段树的工作原理。在你的位置上，我会尝试解决一个可以用它来解决的问题。简单的例子（我知道这个查询可以通过一些预处理在 O(1) 中完成）：矩形范围总和。也就是说：给定一个充满数字的矩阵，回答询问子矩阵总和的查询。在这里，您可以使用一个 semgent 树来分割高度，然后在每个节点上为基于宽度的总和创建一个额外的段树。如果你能做到这一点，那么你就知道关于 2-dim 的一切。段树。下一个挑战是允许更新单个元素——这变得更快更难，因为你必须使用一些“艺术” 正确传播更改（想想段树内的某种类型的缓存）。:)
于 2013-02-09T19:21:05.170 回答