线段树getsum函数错误分析及修正
线段树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函数的错误分析及修正,以及其他相关的建议。
原文地址: https://www.cveoy.top/t/topic/bRAm 著作权归作者所有。请勿转载和采集!