zhengpie @ 2024-05-07 14:35:24
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[114514];
struct segment_tree
{
int sum,add,l,r;
}tree[114514 * 4];
void pushup(int x)
{
tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum;
}
void addtag(int x,int v)
{
tree[x].add += v;
tree[x].sum += v * (tree[x].r - tree[x].l + 1);
}
void pushdown(int x)
{
if(!tree[x].add) return;
addtag(x * 2,tree[x].add);
addtag(x * 2 + 1,tree[x].add);
tree[x].add = 0;
}
void build(int x,int pl,int pr)
{
if(pl == pr)
{
tree[x].l = pl;
tree[x].r = pr;
tree[x].sum = a[pl];
return;
}
int mid = (pl + pr) / 2;
build(x * 2,pl,mid);
build(x * 2 + 1,mid + 1,pr);
pushup(x);
}
int query(int x,int pl,int pr)
{
if(pl <= tree[x].l && tree[x].r <= pr) return tree[x].sum;
pushdown(x);
int res = 0,mid = (pl + pr) / 2;
if(pl <= mid) res += query(x * 2,pl,pr);
if(pr > mid) res += query(x * 2 + 1,pl,pr);
return res;
}
void change(int x,int pl,int pr,int v)
{
if(pl <= tree[x].l && tree[x].r <= pr)
{
addtag(x,v);
return;
}
int mid = (pl + pr) / 2;
if(pl <= mid) change(x * 2,pl,pr,v);
if(pr > mid) change(x * 2 + 1,pl,pr,v);
pushup(x);
}
signed main()
{
//ios::sync_with_stdio(0);
scanf("%lld %lld",&n,&m);
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int bbj = 1,op,x,yyr1345y,k;bbj <= m;bbj++)
{
scanf("%lld",&op);
if(op == 1)
{
scanf("%lld %lld %lld",&x,&yyr1345y,&k);
change(1,x,yyr1345y,k);
}
if(op == 2)
{
scanf("%lld %lld",&x,&yyr1345y);
printf("%lld\n",query(1,x,yyr1345y));
}
}
return 0;
}
by Leonid @ 2024-05-07 15:06:35
@zhengpie
void build(int x,int pl,int pr)
{
tree[x].l = pl;
tree[x].r = pr;
if(pl == pr)
{
tree[x].sum = a[pl];
return;
}
int mid = (pl + pr) / 2;
build(x * 2,pl,mid);
build(x * 2 + 1,mid + 1,pr);
pushup(x);
}
by OneSheeep @ 2024-05-07 15:08:19
@zhengpie
by zhengpie @ 2024-05-07 22:16:25
@OneSheeep 谢谢(说实话,还有一处错误,change里面没有pushdown)