1

给定一个初始化为 0 的数组 arr，即 arr[i]=0 其中 0 < i < n

对其进行了两次操作

  1. 更新 krx

    更新执行以下操作：

    for(i=k;i<=r;i++)
{
    arr[i]=x;
    x+=x;
}

  2. 查询 kr

    查询计算以下总和：

    for(i=k;i<=r;i++)
{
    sum+=arr[i];
}
print(sum);

我的解决方案：
我想到了蛮力，但它很慢。我想到了段树，但是在段树中，更新是按常数执行的，所以它失败了。什么可能是解决这个问题的好算法？

约束

数组的大小是 <=10^5

操作数（更新，查询）<=10^5

4

1 回答 1

2

您正在寻找的是分段树中的延迟传播。我们创建一个大小与段树数组相同的数组lazy[]。这个想法是我们可以通过推迟更新来避免递归调用，并且只在需要时进行更新。

我下面的代码对预定义数据进行更新和求和提取，您可以摆弄 main 以接受所需模式的用户数据并添加 x+=x 等调整。

https://ideone.com/kZsJ0E

我建议您打开代码并并排阅读下面的解释以更好地理解，因为惰性传播通常很难掌握。

这个怎么运作：

  • 最初，lazy[] 数组中的所有条目都设置为 0，这意味着在该节点所代表的范围内没有剩余工作要做。

  • 将数组索引处的段树从 qs（查询开始）更新为 qe（查询结束）：

    -> 如果当前段树节点有任何挂起的更新，那么我们分配该节点 (lazy_value)*(它表示的间隔长度) 并将其子节点的惰性值分配为 new_value

    -> 如果当前节点的范围完全在更新查询范围内。

    i) Update the Current node, by assigning it (lazy_value)*(length of interval it represents)

ii) Postpone updates to children by setting lazy values for children nodes as new_value

    -> 如果当前节点的范围与更新范围重叠，则按照与上述简单更新相同的方法。

    一个。左右孩子重复出现。

    湾。使用左右调用的结果更新当前节点。

  • 现在，当我们使用 get_sum 过程时，如果当前节点有任何未决更新，我们还将更新当前节点并将更新推迟到子节点。

总的来说，这里很难解释惰性传播的整个工作原理，尽管我希望代码和解释有所帮助。

有关延迟传播的更多信息，您可以查看

https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/

于 2016-01-06T15:15:23.243 回答