问题标签 [segment-tree]

我正在从这个页面学习段树：http: //letuskode.blogspot.com/2013/01/segtrees.html

我很难理解各种代码片段。我会一一询问他们。任何帮助将不胜感激。

节点声明：

1.这里的拆分功能会做什么？

2.此代码用于RMQ。所以我认为 val 将是两个段中的最小值并将其存储在其他段中。值将保存在哪里？

范围查询功能：

1.数组树的用途是什么，将保留哪些值？

2.这个语句是什么：tree[root].split(tree[left_child], tree[right_child]); 做 ？

3.这些语句会做什么？：

更新和合并功能：我没有正确理解这两个功能：

另外我应该在主函数中写什么来使这个东西工作？假设我有一个数组 A={2,3,2,4,20394,21,-132,2832} ，如何使用此代码查找 RMQ(1,4)？

所以问题是这样的，我们有一个数组，我们应该做两种类型的操作：

1) 在段 [x,y] 上添加值 v,

2) 在段 [x,y] 上求和

我正在寻找答案，但找不到任何东西，如果您有任何有用的链接或建议，我将不胜感激。

I am writing a lazy propagation code using the segment tree data structures. For doing the lazy propagation I wanted to store a list of integers at a node in the segment tree and while carrying the lazy propagation I wanted to append the list of integers of the node to the left and the right children. In order to maintain the complexity of the update method in Segment Trees to Log(n) time I wanted to do the lazy update at a node in O(1) time. So for storing the list of integers I can use Vectors or LinkedList in Java. Vectors in java have a method called addAll and LinkedList also has the same method. Could anyone please suggest me which one of two would be more optimized for just adding all elements of one list to another. Thanks

给定一个大的未排序数组，我需要找出给定数字在特定范围内的出现次数。（可以有很多查询）

例如，如果 arr []={ 6,7,8,3,4,1,2,4,6,7,8,9}and left_range=3and right_range=7and number=4，则输出将为 2。（考虑到索引为 0 的数组）

arr[i] 可以在 1 到 100000 的范围内。数组最多可以有 100000 个数字。

你能指导我在这里应该使用哪种数据结构或算法吗？

PS：允许对数组进行预处理。

我刚读完段树，时间复杂度为 O(log n) 的插入证明非常有说服力，但我无法弄清楚如何以相同的复杂度执行删除。我还尝试搜索提出分段树但找不到的论文，如果有人有，您可以发布链接。“JL Bentley，Klee 矩形问题的算法。技术报告”

我正在通过使用分段树来解决这个问题。我在每个节点保存总和、最大值、最左边的最大值和最右边的最大值。然后我搜索图表以找到特定区间的答案。我怎样才能提高这段代码的速度？

精简问题：给定一个包含 n 个元素的数组，最初它们都是 0。

您将收到两种类型的查询：0 index1 index2，在这种情况下，您必须将 index1 index2（包括）范围内的所有元素都加一。

第二种类型：1 index1 index2，在这种情况下，您必须打印一个数字来表示 index1 和 index2（包括）之间有多少元素可以被 3 整除。

当然，由于 n 非常大（10^6），好的方法是使用分段树来存储区间，并使用惰性传播来更新 log n 中的树。

但是我实际上真的不知道如何在这里应用惰性传播，因为您必须考虑每个数字的三种可能状态（可能是 3k,3k+1,3k+2），而不仅仅是两个作为翻转硬币问题。

如果我在查询间隔中包含的某个间隔上放置一个标志，我必须查看原始数组及其值来更新它，但是当我必须更新这个间隔的儿子时，我必须做同样的事情再次，这是浪费时间....

有更好的主意吗？我在网上搜索但一无所获...

编辑：我遵循您的建议并编写此代码（C++），并且适用于某些基本情况，但是当我提交它时，我只得到 10/100 分，它有什么问题？（我知道它有点长，没有太多评论，但它是一个具有惰性传播的简单 Segment Tree，如果您有什么不明白的地方，请告诉我！

注意： st[p].zero 包含存储在索引 p 中的间隔为 0 mod 3 的元素，st[p].one 元素 1 mod 3 和 st[p].two 元素 2 mod 3；当我更新时，我将这些元素（0->1、1->2、2->0）移动一个位置并使用惰性。更新时，我返回一个pair < int , pair< int, int >> ，只是存储三组数字的简单方法，这样a可以返回数字0,1,2 mod 3的差。

如果我们想更新一个范围内的值，谁能告诉我延迟传播在段树中是如何工作的？另外，我们如何使用分段树和惰性传播来解决这个问题？

假设一排有 15 个男孩，面向东站着，我们说经过 3 次移动后，从 [3,6] 开始的范围将朝北，经过 2 次移动后，他们将面向西方。^{如果我们的行大小在 10 6}左右，我们将如何更新范围？

顺时针方向[东-->南-->西-->北-->东]

例如：假设最初有 n 个学生面向东站着，我们说我们必须将学生 3 到 6 顺时针方向移动两次。这样一来，搬家后，学生们就会像“eewweee e”一样。然后，我们想找到面向同一方向站立的范围内的最大学生数。在这个例子中，如果我们要在 [1,6] 范围内找到答案，那么有 2 个面向东的学生和 4 个面向西方的学生，所以答案是 4。

我正在解决段树和四叉树相关的问题；虽然我注意到在段树中，我们将一维数组分成2 个（2^1）段并递归地执行此操作，直到基本情况到达。同样，在四叉树中，我们将 2D 网格细分为4 (2^2)同样，在四叉树中，我们在每一步所有这些分治机制都是为了实现对数时间复杂度。没有冒犯的意思！

但是为什么我们不将数组细分为4 (4^1) 个或更多部分而不是分段树中的 2 个部分呢？为什么我们不将网格分成16 (4^2) 个部分而不是 4 个？通过这样做，我们可以实现O(log(N))性能，但它会更好log，因为log(N)(base 4) 比log(N)(base 2) 更好。

我知道在这种情况下，实施会有点困难。是否存在内存开销问题？还是什么？

如果我在任何地方错了，请纠正我。谢谢！

给定一个包含N个数字的数组A（全为正数且包含小于或等于 4 位数字），将支持2种类型的查询。总共有 M 个查询。

1. 用K更新由索引L,R（包括两者）给出的范围。
2. 返回L,R（包括两者）给定范围内的最大元素。

将数字更新K次意味着将数字旋转K次。

例如 1234 旋转成 2341

905转成059，059转成590。

注意：059 和 59 是不同的数字。59 转为 95。

给定的数组元素没有前导零。

约束：

0 <= Ai < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

我想到了一个分段树，其中树节点存储它们包含的范围的旋转次数。我用惰性传播实现了这一点，但也使用惰性传播，我的查询实现在最坏的情况下需要 O(N) 时间，这会导致 TIME LIMIT EXCEEDED。

任何人都可以提出更快的方法吗？

我是否缺少数组或结构的某些属性？