问题标签 [segment-tree]

我想在 C++ 中编写段树代码并通过递归编写代码查询操作，但它很慢并且给出了 TLE。因此，有人可以通过迭代建议和解释以下代码，这将是一个很大的帮助。提前致谢。

以下代码在一个范围内计算 gcd

这里 ，

T段树

ss -segment 开始

se段结束

index - 段树的当前节点

L - 查询下界

R - 上界

我们有一个数组arr[0 . . . n-1]。我们应该能够

1. 求从索引 L 到 R 的元素之和，其中 0 <= L <= R <= n-1 。
2. 更改数组中指定元素的值，arr[i] = x其中 0 <= i <= n-1。

这可以有效地使用分段树来解决。

但是如何解决与此相反的问题，即

1. 求从索引 0 到 n-1 的所有元素 (arr[i]) 的总和，不包括 L<= i <= R，其中给出了 L 和 R。
2. array arr[i] = x更改where 0 <= i <= n-1的指定元素的值。

如何像段树一样有效地解决上述问题？

我正在尝试解决这个问题。

我找到了这个问题的教程，但我不知道如何构建分段树，它会在 O(log n) 中找到小于 x 的数字量（x 可以改变）。在教程中它被省略了。

谁能解释我该怎么做？

给定一个序列 A，其中包含 -10000 到 10000 之间的 N (N <= 50000) 个整数。在此序列上，您必须应用 M (M <= 50000) 操作：修改序列中的第 i 个元素或给定 xy打印最大值{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }。

问题链接

我为此使用段树，但没有得到正确的输出，请帮助我在哪里犯了错误
代码：

制作树：

更新功能

查询功能：

我不知道我在哪里犯了错误请帮助，dp array即 dp 的大小需要多少存储容量

我在 spoj 中 使用分段树中的惰性传播来解决 GSS3。我参考了这个博客： 惰性传播

我应该如何使用惰性传播来解决这个问题，我不明白这个博客中是如何使用惰性数组的？

这是问题链接 - QSET - Codechef

这是编辑链接 - QSET - 编辑

基本上，该问题查询某个范围[L, R]中子字符串的数量。我已经实现了一个段树来解决这个问题。我密切关注社论。

我创建了一个struct来表示段树的一个节点。

有人可以向我解释如何使这个程序更快吗？我猜更快的 I/O 是这里的关键。是这样吗？

我正在为更大的测试用例获取 TLE，即子任务 3 和 4（检查问题页面）。对于子任务 1 和 2，它被接受。

[www.codechef.com/viewsolution/5909107] 是一种公认​​的解决方案。它具有几乎相同的代码结构，除了scanf使用它代替cin. 但是，我关掉了，sync_with_stdio所以这不应该是一个差异化因素，对吧？

我正在学习段树（以范围最小查询为例）并且在理解查询段树的算法部分背后的原因时遇到了一些问题。

我理解构建段树的部分没有问题，我不明白为什么在这个函数中：

如果该节点的段是给定范围的一部分，则返回该段的最小值。

我目前正在fseek()程序中使用。我还维护了一个字节数组，用于跟踪文件内打印的每一行的字节。我还使用段树，以便更快地访问特定位置。另外，我不允许使用其他任何东西......（如结构）有没有办法这样做？

我知道段树可用于查找 A 的子数组的总和。根据此处的教程，这可以在 O(logn) 时间内完成。

但是我无法证明查询时间确实是 O(logn)。这个链接（和许多其他链接）说我们可以证明在每个级别，处理的最大节点数是 4，因此 O(4logn) == O(logn)。但是我们如何证明这一点，也许通过矛盾？

如果是这样，如果我们将段树用于高维数组的范围和，如何扩展证明？

例如，我可以考虑通过将原始矩阵划分为 4 个象限（类似于线性数组中的减半间隔）来构建一个象限段树来找到子矩阵和，但我无法证明这一点。

链接：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)]。由于树是使用数组表示的，并且必须维护父索引和子索引之间的关系，因此为段树分配的内存大小将为 .

这么多内存是如何分配的（上段的最后一行）？如果正确，父子索引如何存储在代码中？请给出这背后的原因。如果这是错误的，那么正确的值是多少？