线段树错误排查:更新和查询函数优化
线段树错误排查:更新和查询函数优化
在使用线段树进行区间更新和查询操作时,经常会遇到一些错误。本文将重点介绍 update 和 getsum 函数中常见的错误以及优化方法。
错误分析
线段树使用延迟标记来优化区间更新操作。当对一个节点进行更新时,我们不会立即更新其子节点,而是将更新信息存储在延迟标记中。在需要查询子节点信息时,再根据延迟标记进行更新。
然而,在 update 和 getsum 函数中,如果没有正确处理延迟标记,会导致子节点的值没有被及时更新,从而出现计算错误。
优化方法
为了避免上述错误,我们需要在 update 和 getsum 函数中添加对延迟标记的处理。
1. update 函数优化
在 update 函数中,我们需要在更新当前节点之前,先判断延迟标记是否为 0。如果延迟标记不为 0,则需要更新子节点的值,并将延迟标记清零。
void update(int l, int r, ll d, int s, int e, int k)
{
if (l <= s && e <= r)
{
tree[k] += (e - s + 1) * d, mark[k] += d;
return;
}
int m = getM(s, e);
if (mark[k] && s != e)
{
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)
{
update(l, r, d, s, m, lSon(k));
}
if (r > m)
{
update(l, r, d, m + 1, e, rSon(k));
}
tree[k] = tree[lSon(k)] + tree[rSon(k)];
}
2. getsum 函数优化
在 getsum 函数中,同样需要在查询当前节点之前,先判断延迟标记是否为 0。如果延迟标记不为 0,则需要更新子节点的值,并将延迟标记清零。
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;
}
代码示例
以下是完整的代码示例:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int lSon(int k) { return k << 1; }
int rSon(int k) { return (k >> 1) + 1; }
int getM(int s, int e) { return s + ((e - s) >> 1); }
int n, m;
ll a[N], tree[N << 2], mark[N];
void built(int s, int e, int k)
{
if (s == e)
{
tree[k] = a[s];
return;
}
int m = getM(s, e);
built(s, m, lSon(k)), built(m + 1, e, rSon(k));
tree[k] = tree[lSon(k)] + tree[rSon(k)];
}
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;
}
void update(int l, int r, ll d, int s, int e, int k)
{
if (l <= s && e <= r)
{
tree[k] += (e - s + 1) * d, mark[k] += d;
return;
}
int m = getM(s, e);
if (mark[k] && s != e)
{
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)
{
update(l, r, d, s, m, lSon(k));
}
if (r > m)
{
update(l, r, d, m + 1, e, rSon(k));
}
tree[k] = tree[lSon(k)] + tree[rSon(k)];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
built(1, n, 1);
while (m--)
{
int cmd;
scanf("%d", &cmd);
if (cmd == 1)
{
int x, y;
ll k;
scanf("%d%d%lld", &x, &y, &k);
update(x, y, k, 1, n, 1);
}
else
{
int x, y;
scanf("%d%d", &x, &y);
printf(":%lld\n", getsum(x, y, 1, n, 1));
}
}
return 0;
}
总结
通过对 update 和 getsum 函数进行优化,我们可以避免线段树中常见的错误,确保延迟标记能够正确更新子节点的值,从而得到准确的计算结果。
原文地址: https://www.cveoy.top/t/topic/bRAs 著作权归作者所有。请勿转载和采集!