我最近接触到一种名为“线段树”的新的数据结构，然后了解到它也可以扩展到两个维度，但是我找不到一个好的来源来阅读其实现细节和其他相关内容。 我希望从使用它来参加编程比赛的角度来学习它，而不是从图形领域的角度。对于一些可以使用它解决的问题也会很有用。 请问是否有好的来源可以推荐给我阅读？ 谢谢。
3个回答
2
将以下文本翻译成中文：
将线段树扩展到多维，特别是在编程竞赛中，可能会非常困难和耗时。
如果您需要多个维度，则应首先了解二进制索引树，然后尝试将其扩展到多个维度。
二进制索引树是一种数据结构，在某些情况下比线段树表现更好，而在其他情况下则不适用。
使用线段树时，扩展到多个维度是微不足道的。
在这里，您可以找到有关它们的文章。
在这里，您可以找到一个问题，可以帮助您测试实现。
- Spatarel
1
有一篇关于一维线段树及其二维推广的好文章，其中包含代码示例。但是它是俄语的，所以您可能只需要关注代码示例 =)
- K. Bulatov
0
我不确定你是否能够找到更多相关信息。我认为人们需要理解k维区间树的工作原理。如果我处于你的位置，我会尝试解决一些可以用它来完成的问题。一个简单的例子（我知道这个查询可以通过一些预处理在O（1）内完成）：矩形范围求和。即：给定一个填有数字的矩阵，回答询问并求出子矩阵的总和。 您可以使用一个区间树将其分裂成高度，并在每个节点上创建一个基于宽度的求和的附加区间树。 如果您能做到这一点，那么你就知道所有关于二维区间树的知识了。 下一个挑战是允许更新单个元素 - 这变得更加困难，因为您必须使用一些“技巧”来正确传播更改（想象一下段落树内部的某种缓存技术）。 ：）
- Amtrix
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接