线段树getsum函数错误分析及修正

在使用线段树进行区间查询时,getsum函数是核心函数之一。本文将分析getsum函数中常见的错误,并提供修正方案。

错误分析

在getsum函数中,当mark[k]不为0时,需要更新tree[lSon(k)]和tree[rSon(k)]的值,而不是累加mark[k]的值。

修正方案

以下是对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;
}

其他建议

建议在使用线段树之前对数组a进行初始化,避免出现未定义的情况。

完整代码

#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;
}

希望以上内容能够帮助您理解线段树getsum函数的错误分析及修正,以及其他相关的建议。

线段树getsum函数错误分析及修正

原文地址: https://www.cveoy.top/t/topic/bRAm 著作权归作者所有。请勿转载和采集!

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