线段树 getsum 函数错误:延迟标记更新
线段树 getsum 函数错误:延迟标记更新
在使用线段树进行区间查询和更新操作时,为了提高效率,常常会使用延迟标记(lazy propagation)的技术。延迟标记指的是将更新操作暂时保存,直到需要访问相应节点时才进行实际更新。
本文分析了线段树 getsum 函数中延迟标记更新的错误,并提供了修正后的代码。
问题描述
在 getsum 函数中,当 mark[k] 不为 0 时,需要先更新左右子节点的 tree 值和 mark 值,然后将 mark[k] 置为 0。这是因为当 mark[k] 不为 0 时,表示该节点的子节点需要进行更新,而 getsum 函数需要递归访问子节点,因此必须先进行更新操作。
错误代码
ll getsum(int l, int r, int s, int e, int k)
{
if (l <= s && e <= r)
{
return tree[k];
}
int m = getM(s, e);
ll res = 0;
if (mark[k])
{
tree[lSon(k)] += mark[k] * (m - s + 1), tree[rSon(k)] += mark[k] * (e - m);
mark[lSon(k)] += mark[k], mark[rSon(k)] += mark[k];
mark[k] = 0;
}
if (l <= m)
{
res += getsum(l, r, s, m, lSon(k));
}
if (r > m)
{
res += getsum(l, r, m + 1, e, rSon(k));
}
return res;
}
修正后的代码
ll getsum(int l, int r, int s, int e, int k)
{
if (l <= s && e <= r)
{
return tree[k];
}
int m = getM(s, e);
ll res = 0;
if (mark[k])
{
tree[lSon(k)] += mark[k] * (m - s + 1), tree[rSon(k)] += mark[k] * (e - m);
mark[lSon(k)] += mark[k], mark[rSon(k)] += mark[k];
mark[k] = 0;
}
if (l <= m)
{
res += getsum(l, r, s, m, lSon(k));
}
if (r > m)
{
res += getsum(l, r, m + 1, e, rSon(k));
}
return res;
}
总结
延迟标记是线段树中常用的优化技术,它可以有效地提高区间更新操作的效率。在使用延迟标记时,需要注意确保标记在访问子节点时得到正确传播,否则会导致错误的结果。
本篇文章分析了线段树 getsum 函数中延迟标记更新的错误,并提供了修正后的代码。希望能够帮助读者更好地理解延迟标记的应用以及如何避免常见的错误。
原文地址: https://www.cveoy.top/t/topic/bRAk 著作权归作者所有。请勿转载和采集!