线段树错误排查:更新和查询函数优化

在使用线段树进行区间更新和查询操作时,经常会遇到一些错误。本文将重点介绍 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 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录