LabmemNo_012LzTopic @ 2024-10-31 13:34:36
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std;
#define Max 100005
int tree[Max * 4] = { 0 }, a[Max] = { 0 }, k;
int creattree(int u, int l, int r)
{
if (l == r)
{
return tree[u] = a[l];
}
int imd = (l + r) / 2;
return tree[u] = creattree(u * 2, l, imd) + creattree(u * 2 + 1, imd + 1, r);
}
void treewh(int u, int l, int r, int x)
{
tree[u] += k;
if (u == x)return;
int imd = (l + r) / 2;
if (x >= l && x <= imd)treewh(u * 2, l, imd, x);
else treewh(u * 2 + 1, imd + 1, r, x);
return;
}
int querytree(int u, int l, int r, int L, int R)
{
int imd = (l + r) / 2;
if (l == L && r == R)return tree[u];
if (imd < L)
{
return querytree(u * 2 + 1, imd + 1, r, L, R);
}
else if (imd + 1 > R)
{
return querytree(u * 2, l, imd, L, R);
}
else
{
return querytree(u * 2, l, imd, L, imd) + querytree(u * 2 + 1, imd + 1, r, imd + 1, R);
}
}
int main()
{
int n, m, t, x, y;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
creattree(1, 1, n);
while (m--)
{
cin >> t >> x >> y;
if (t == 1)
{
cin >> k;
for (int i = x; i <= y; i++)
{
treewh(1, 1, n, i);
}
}
else
{
printf("%d\n", querytree(1, 1, n, x, y));
}
}
return 0;
}
by ljmmmmm @ 2024-10-31 14:11:56
27行改成
if (l == x&& l == r)return;
试试
by ljmmmmm @ 2024-10-31 14:13:29
帮你试了,70分tle,区间修改记得用懒惰标记
by 添哥 @ 2024-10-31 14:14:33
for (int i = x; i <= y; i++)
{
treewh(1, 1, n, i);
}
@LabmemNo_012LzTopic 做
by 添哥 @ 2024-10-31 14:15:22
去学下懒惰标记吧
by LabmemNo_012LzTopic @ 2024-10-31 20:16:54
@ljmmmmm 感谢!!!Orz
by LabmemNo_012LzTopic @ 2024-10-31 20:18:07
@添哥 好的!!!