问题标签 [segment-tree]

我有以下代码，用于具有延迟传播的分段树，我可以设法编写。此代码不适用于将某个范围内的所有数字与一个值相乘，例如 x。我认为我在 update_mult 函数中做错了什么。树维护范围的总和。

我无法弄清楚 update_mult 的问题。专家，你能帮我找出我在实施中哪里出了问题吗？

这是 SPOJ“SEGSQRSS - 带段树的平方和”的问题，该问题的链接是http://www.spoj.com/problems/SEGSQRSS/我正在尝试使用惰性传播但找不到正确的解决方案，任何人都可以在我出错的地方提供帮助。

提前致谢。

我正在尝试来自 spoj 的 HORRIBLE 问题，这是链接：http ://www.spoj.com/problems/HORRIBLE/我正在尝试用分段树自学惰性传播。以下是我编写的代码，我尽量使其简洁明了，如果有不清楚的地方请告诉我。

提供的示例测试用例用我的代码给出了正确的答案，但是在提交时，我收到了错误的答案消息。我已经检查了很多次我的代码，但我找不到错误。

任何帮助表示赞赏。谢谢！

我一直想知道是否只有当更新的新值小于当前值时才可以更新段树。

例如。a[i]toa[j]是更新到 x

如何才能做到这一点？

延迟传播是我正在尝试的。

我可以在有条件的 BIT 中执行范围更新吗？假设我有一组负频率和正频率 A[] = {1, -3, -4, 5, 9}。而且我想用一个条件来更新数组的值：如果更新值（x）为负，则仅更新负元素，如果更新值为正，则仅更新范围内的正值。

例如，在上述数组中，如果更新查询为 2 4 -2，（左右值），则只更新第 2（-3）和第 3（-4）位置。离开第 4(5) 个位置，因为它是一个正整数。

或者我应该使用另一个数据结构来完成这个？

我用它来学习范围更新。

给定 N 个工作，其中每个工作由以下三个元素表示。

1) 开始时间

2) 完成时间。

3) 利润或相关价值。

找到工作的最大利润子集，使得子集中没有两个工作重叠。

我知道一个动态编程解决方案，其复杂度为 O(N^2)（接近 LIS，我们必须检查之前的元素，我们可以将当前区间与这些元素合并，并取其合并最大的区间，直到第 i 个element )。这个解决方案可以使用二分搜索和简单排序进一步改进到 O(N*log N)！

但是我的朋友告诉我，它甚至可以通过使用分段树和二分搜索来解决！我不知道我将在哪里使用 Segment Tree 以及如何使用 .??

你能帮我吗？

根据要求，抱歉没有评论

我正在做的是根据起始索引进行排序，通过合并先前的间隔和它们的最大可获得值，将最大可获得值存储到 i 在 DP[i] ！

编辑： 我的工作代码终于花了我 3 个小时来调试它！Morover 由于较大的常量和糟糕的实现，此代码比二进制搜索和排序慢：P（仅供参考）

这是使用段树的 rmq。但我没有得到正确的输出，谁能告诉我我错在哪里。
`

`
此代码的输出：
0
1-2 范围内的预期输出为 2 函数 get_min_util 从 if 条件返回 0，其中注释 ////////c1 被写入

所以我再次需要一些帮助。我最近开始在 codechef 上做中级问题，因此我得到了很多 TLE。

所以基本上问题是找到问题中给出的多个最大范围查询的总和。给出初始范围，然后通过问题中给出的公式计算下一个值。

我使用段树来解决问题，但我一直在为一些子任务获取 TLE。请帮我优化这段代码。

问题链接 - https://www.codechef.com/problems/FRMQ

我正在使用此段树实现来查找范围内的最大元素：

主要是我在做这样的事情：

但它给出了错误的结果。就像输入 N=5 和 M=1 和数组是 [3,1,3,2,1] 查询 L=1,R=1 它给出 8。请帮助查找错误。

我找不到我的代码有什么问题:(

我解决了代码中显示的给定问题，但我得到了错误的答案。我使用了分段树方法。节点包含 max1（给定范围内的最大数量）和 sum（给定范围内两个数量的最大总和）。请帮忙。