SuAnRan @ 2023-05-14 16:54:29
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
LL sum[500000], easy[500000]; // Sum求和数组, 懒惰数组
LL A[500000], n, m;
void pushUP(int x)
{
sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
void Build(int l, int r, int x) // 建立线段树
{
if(l == r)
{
sum[x] = A[l];
return;
}
int m = l + r >> 1;
Build(l, m, x * 2);
Build(m + 1, r, x * 2 + 1);
pushUP(x);
}
void point_Update(int L, int C, int l, int r, int x) // 单点修改
{
if(l == r)
{
sum[x] += C;
}
int m = l + r >> 1;
if(L <= m) point_Update(L, C, l, m, x * 2);
else point_Update(L, C, m + 1, r, x * 2 + 1);
pushUP(x);
}
void PushDown(int l, int r, int x) //懒标记下推
{
if(easy[x])
{
easy[x * 2] += easy[x];
easy[x * 2 + 1] += easy[x];
//修改sum值
int mid = l + r >> 1;
sum[x * 2] += easy[x] * (mid - l + 1);
sum[x * 2 + 1] += easy[x] * (r - mid);
easy[x] = 0;
}
}
void range_Update(int L, int R, int C, int l, int r, int x) //区间修改
{
if(l == L && r == R)
{
sum[x] += C * (r - l + 1);
easy[x] += C;
return ;
}
int m = l + r >> 1;
PushDown(l, r, x);
if(L <= m) range_Update(L, R, C, l, m, x * 2);
if(R > m) range_Update(L, R, C, m + 1, r, x * 2 + 1);
pushUP(x);
}
LL Query(int L, int R, int l, int r, int x) // 查询【L~R】的和
{
if(L == l && r == R) //如果在
{
return sum[x];
}
// 否则, 推下标
PushDown(l, r, x);
int m = l + r >> 1;
LL ans = 0;
if(L <= m) ans += Query(L, R, l, m, x * 2);
if(R > m) ans += Query(L, R, m + 1, r, x * 2 + 1);
return ans;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> A[i];
Build(1, n, 1);
while(m --)
{
int op;
cin >> op;
if(op == 1)
{
int l, r, x;
cin >> l >> r >> x;
range_Update(l, r, x, 1, n, 1);
}
else
{
int l, r;
cin >> l >> r;
cout << Query(l, r, 1, n, 1) << endl;
}
}
}
by hjqhs @ 2023-05-14 17:00:25
你main函数外定义了m 但在部分线段树操作函数中写的是m=(l+r)>>1
by hjqhs @ 2023-05-14 17:00:50
然后不需要point update