分段树中的数据映射和惰性传播
看起来整个互联网上只有一篇关于线段树中懒惰标记的好文章，它是：http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296 我理解了只更新查询节点并标记其子节点的概念。但我的问题是，如果我先查询子节点，然后再查询父节点呢？ 在这棵树中（还包括...
使用线段树从给定的数组中找到最大的子数组和
我想要从给定的数组中找到最大和的连续子数组。我知道使用动态规划概念和Kadane算法来找到最大和连续子数组的O(n)方法。 但是如果区间查询的数量非常大，这将需要很长时间。是否有一种方法可以使用线段树解决它，因为它是最好的选项，能够在O(log(n))时间内回答区间查询。 谢谢。
区间树、线段树、二叉索引树和范围树有哪些区别？
段树、区间树、二叉索引树和范围树在以下几个方面有何不同： 关键思想/定义 应用场景 性能/高维度顺序/空间消耗 请勿仅提供定义。
O(lg N)时间复杂度下的逆序对数量范围查询
给定一个未排序的包含n个整数的数组，我知道可以使用BIT在O(N lg N)的时间复杂度内找到逆序对的总数，具体方法请参考Count Inversion by BIT。 但是，如果我需要查询任意范围内逆序对的总数，是否可能在O(lg N)的时间复杂度内完成？ 可以接受O(N lg N)的预...
在C++中，用于线段树的STL
是否有适用于线段树的STL库？ 在竞赛编程中，编写线段树代码需要花费大量时间。我想知道是否有适用于线段树的STL库，以便节省大量时间。
在二维平面上拟合线段
我遇到了以下问题 给定一个大小为N x S的网格和m个与水平轴平行的线段（它们都是元组(x'，x''，y)），回答Q个在线查询的形式为(x'，x'')。这种查询的答案是最小的y（如果有的话），使得我们可以放置一条线段（x'，x''，y）。所有线段都不重叠，但一个线段的开始可以是另一个线段的结...
Python中的线段树实现
我正在使用线段树解决这个问题，但我得到了时间限制错误。以下是用于区间最小查询的原始代码，并通过在我的代码中更改min为max来解决上述问题。我不知道如何改进代码的性能。你可以帮我优化一下吗？ t = [None] * 2 * 7 # n is length of list de...
线段树数组的内存是多少？2 * 2 ^(ceil(log(n))) - 1。
该链接: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/。以下是引用的文本: 我们从一个段arr [0 ... n-1]开始。 每次我们将当前段分成两半（如果它尚未成为长度为1的段），然后在这两个部分上调...
树状数组与线段树的比较
我需要在一个数组的范围内计算总和，于是我了解了线段树和树状数组（Fenwick Tree），发现这两个数据结构都具有相同的渐进运行时间来查询和更新。我进行了更多的研究，发现这两个数据结构可以以相同的速度完成所有操作。两者都具有线性的内存使用（线段树的内存使用量是树状数组的两倍）。 除了运行时间...