问题标签 [lazy-propagation]

以下是http://www.spoj.pl/problems/LITE/使用 Segment Tree 和惰性传播的实现。我是分割树的新手，我不明白为什么我会得到 TLE。有人可以看看它并帮助我纠正我的错误吗？

好吧，我试图在 Codechef 上解决这个翻转硬币的问题。正在用段树解决它。但获得时间限制超过。我搜索了一下，发现必须使用惰性传播。但我无法理解。我的更新功能递归工作（从上到下）。请给出一些提示或举例说明。还要指出我必须更改代码的地方。

在掷硬币时，如果节点值为 1，则在更新期间将其更改为 0，如果为 0，则将其更改为 1。

start 和 end 是原始数组的限制。tree 是段树数组。

精简问题：给定一个包含 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的差。

给定一个包含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。

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

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

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

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

我有很多查询的问题，有四种类型：

1. 添加到范围。

2. 初始化一个范围。

3. 将范围与标量相乘。

4. 在一个范围内查找运行总和。

由于查询数量庞大，我必须使用带有延迟传播的分段树，但我一直坚持如何在超过 2 种类型的查询上使用延迟传播。我如何能够确定稍后要进行更新时，要进行哪种类型的更新（即加法、乘法、初始化）？

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

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

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

我有一个问题，需要一个可以处理 2 个操作的结构：

1. 将节点的值从位置 x 更改为位置 y 到 newValue。

2. 获取从位置 a 到 b 的值的总和。

节点数为 50000，查询数为 50000。我试图用延迟更新实现 IT 树，但我不知道如何。第一个操作与通常的加法和乘法操作有些不同。

如何为段树实现惰性传播，其中我们有两种类型的查询，一种用于查找给定范围内的最大元素，另一种是将给定范围内的元素除以一个数字（对于所有元素不一定相同，比如每个元素除以其最小的奇数因子或类似的东西）？

我在段树的延迟传播中面临一个问题。我有一个数组A，长度为 N ，较小的数组（最大长度为 20）。我还有一个索引数组B ，指的是我当前在数组Ai中指向的索引。

有 2 个操作，： a) 更新B的指针以指向给定范围的下一个元素。b) 打印给定范围内指针当前指向的最大值。

例如：-

在查询范围 1,2 时，最大值为 8。这是因为数组 B 的指针指向数组的第一个元素。所以我们正在使用 1,8。

在进行 2,3 max =8 的查询时；这是因为我们正在使用值 8,3。一般来说，

这是非常简单的两种方法。但是，由于输入限制较大，我需要 O(logn) 查询和更新时间。这就是为什么我想到使用段树的原因（目前它的复杂性是 O(n^2)。但是我似乎无法弄清楚如何更新延迟传播中的中间节点。

任何见解都会有所帮助。另外，如果您可以在线链接任何类似的问题，那将非常有帮助，因为我做不到（我不知道这样的问题不是来自任何网站）。感谢您的任何帮助。

注意：如果b[i]>a[i].length然后替换a[i][b[i]]为 1。