标签: segment-tree

在以下方面,段树,间隔树,二进制索引树和范围树之间有什么区别:

• 关键思想/定义
• 应用
• 更高维度/空间消耗的性能/订单

请不要只给出定义.

链接:http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/.这是引用的文字:

我们从段arr [0开始...N-1].每当我们将当前段分成两半时(如果它还没有成为长度为1的段),然后在两半上调用相同的过程,并且对于每个这样的段,我们将总和存储在相应的节点中.除最后一级之外,构造的分段树的所有级别都将被完全填充.此外,树将是一个完整的二叉树,因为我们总是在每个级别将两个分段分成两半.由于构造的树总是具有n个叶子的完整二​​叉树,因此将存在n-1个内部节点.所以节点的总数将是2n-1.段树的高度将是ceil [log(n)].由于树是使用数组表示的,并且必须维护父索引和子索引之间的关系,因此为分段树分配的内存大小将为2*2 ^(ceil(log(n))) - 1.

如何分配内存(上面的para的最后一行)那么多？如果父代码和子代码索引正确,它们如何存储在代码中？请在此背后给出推理.如果这是假的那么什么是正确的值？

看起来在整个互联网上的Segment Tree中只有一篇关于延迟传播的好文章,它是:http: //www.spoj.pl/forum/viewtopic.php？f = 27&t = 8296

我理解只更新查询节点并标记其子节点的概念.但我的问题是,如果我先查询子节点,然后再查询父节点.

在这棵树中(以及堆数组中的位置)

           0->[0 9]
      1->[0 4]    2->[5 9]
   3->[0 2] 4->[3 4]  5->[5 7] 6->[8 9]
 .....................................

第一个查询,如果我更新[0 4],它的数据将被更改,其子项将被标记.第二个查询,是段[0 9]的读状态.

我在这里面对这个问题.我的分段树实现使得每个节点的值是其左右子节点的总和.因此,当我更新节点的值时,我要更新它的所有父节点.为了解决逻辑问题,现在我正在更新节点的所有父节点(直到它到达树的根).但这会带来性能损失,我使用分段树进行快速批量更新的整个目的正在被杀死.

任何人都可以解释一下,我在使用分段树时出错了吗？

你知道Java中(二进制)段树的良好实现吗？

我已经阅读了一些关于两个常见数据结构的教程,这些数据结构可以在O(lg N)中实现范围更新和查询:段树和二进制索引树(BIT/Fenwick树).

我发现的大多数例子都是关于一些关联和交换操作,如"范围内的整数和","范围内的XOR整数"等.

我想知道这两个数据结构(或任何其他数据结构/算法,请提出)是否可以在O(lg N)中实现以下查询？(如果没有,O(sqrt N)怎么样)

给定一个整数A的数组,查询范围[l,r]中的不同整数的数量

PS:假设可用整数的数量是~10 ^ 5,那么 used[color] = true或者位掩码是不可能的

例如:A = [1,2,3,2,4,3,1],查询([2,5])= 3,其中范围索引是从0开始的.

我需要计算数组范围内的总和，所以我遇到了 Segment Tree 和 Fenwick Tree，我注意到这两种树都以相同的渐近运行时间进行查询和更新。我做了更多的研究，这两种数据结构似乎以相同的速度完成所有事情。两者都具有线性内存使用量（段树使用量是其两倍）。

除了运行时间/内存和实现中的恒定因素之外，还有什么理由让我选择一个而不是另一个？

我正在寻找一个客观的答案，例如某些操作比另一个更快，或者可能某个限制另一个没有。

我看到了另外 2 个关于此的 StackOverflow 问题，但答案只是描述了这两种数据结构，而不是解释何时一个可能比另一个更好。

我想找到给定数组中最大的和连续子数组.我知道使用Kadane算法使用动态规划的概念找到最大和连续子阵列方法的O(n)方法.

但是如果范围查询的数量非常大,则需要花费很多时间.有没有办法使用Segment-Trees来解决它,因为它是在O(log(n))时间内解决范围查询的首选方案.谢谢.

我遇到了以下问题的麻烦

给定N x S网格和m个平行于水平轴的段(所有这些都是元组(x',x'',y)),回答形式(x',x'')的Q在线查询.这种查询的答案是最小的y(如果有的话),这样我们就可以放置一个段(x',x'',y).所有段都是非重叠的,但是一个段的开头可以是另一个段的结尾,即允许段(x',x',y)和(x'',x'',y).能够放置一个段意味着可能存在一个段(x',x'',y)不会违反规定的规则,段实际上并未放置(具有初始段的板未被修改)但我们只说明可能有一个.

约束

1 ? Q, S, m ? 10^5
1 ? N ? 10^9

Time: 1s
Memory: 256 Mb

以下是以下链接中的示例.输入段是(2,5,1),(1,2,2),(4,5,2),(2,3,3),(3,4,3).
回答查询

1)(1,2)→1

2)(2,3)→2

3)(3,4)→2

4)(4,5)→3

5)(1,3)→不能放置一个段

第三个查询的可视化答案(蓝色部分):

我不太明白如何处理这个问题.它应该用持久的分段树来解决,但我仍然无法想出一些东西.

请问你能帮帮我吗.

这不是我的功课.源问题可以在http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614找到.可用的语句没有英文版本,测试用例以不同的方式显示输入数据,所以不要介意源.

我正在尝试解决这个问题：https : //cses.fi/problemset/task/1144/

给定一个最多200000包含元素的数组，我的任务是处理最多200000查询，这些查询要么让我更新数组中的单个值，要么让我找到给定范围内的 a 和 b 之间的元素数（对于例如，查询会询问从索引1到5范围内有多少元素[2, 3]）。

我目前的想法是首先对给定数组中的值使用索引压缩（因为值可以高达10^9，因此保留一个简单的出现数组会超出存储限制），然后保留另一个包含每个压缩出现次数的数组数字。然后，可以使用求和段树来处理和更新查询。

但是，我在尝试实施这种方法时遇到了问题。我意识到更新单个数组值会迫使我更改压缩数组。

例如，给定一个数组[1, 5, 3, 3, 2]，我将定义一个压缩函数C，使得

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

然后，出现数组将是[1, 1, 2, 1]，并且处理总和查询将是有效的。但是，如果我被指示更新一个值，例如，将第三个元素更改为4，那么这会使所有内容失去平衡。压缩功能必须更改为

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

这将迫使我重建我的事件数组，从而导致O(N)更新时间。

由于N可以达到200000，我目前的方法不能有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？

我正在使用段树解决这个问题,但我得到时间限制错误.下面是我的范围最小查询的原始代码,通过在我的代码中更改,可以解决上述问题.我不知道如何提高代码的性能.你能帮我解决它的性能问题吗？minmax

t = [None] * 2 * 7      # n is length of list


def build(a, v, start, end):
    '''
    A recursive function that constructs Segment Tree for list a.
    v is the starting node
    start and end are the index of array
    '''

    n = len(a)
    if start == end:
        t[v] = a[start]
    else:
        mid = (start + end) / 2
        build(a, v * 2, start, mid)     # v*2 is left child of …