wangxinyu5483 @ 2024-11-07 20:24:08
#include<bits/stdc++.h>
using namespace std;
#define ls 2*p
#define rs 2*p+1
long long a[10000000],tag[10000000],n,m,tree[10000000];
void tagdown(long long pl,long long pr,long long p)
{
long long mid=(pl+pr)>>1;
if(tag[p]>0)
{
tag[ls]+=tag[p];
tag[rs]+=tag[p];
tree[ls]+=(mid-pl+1)*tag[p];
tree[rs]+=(pr-mid)*tag[p];
tag[p]=0;
}
}
void change(long long l,long long r,long long v,long long pl,long long pr,long long p)
{
if(l<=pl&&pr<=r)
{
tag[p]+=v;
tree[p]+=v*(pr-pl+1);
return ;
}
tagdown(pl,pr,p);
long long mid=(pl+pr)>>1;
if(l<=mid)
{
change(l,r,v,pl,mid,ls);
}
if(r>mid)
{
change(l,r,v,mid+1,pr,rs);
}
}
long long ask(long long l,long long r,long long pl,long long pr,long long p)
{
if(l<=pl&&pr<=r)
{
return tree[p];
}
tagdown(pl,pr,p);
long long mid=(pl+pr)/2;
long long ans=0;
if(l<=mid)
{
ans+=ask(l,r,pl,mid,ls);
}
if(r>mid)
{
ans+=ask(l,r,mid+1,pr,rs);
}
return ans;
}
void update(long long p)
{
tree[p]=tree[ls]+tree[rs];
}
void build(long long p,long long pl,long long pr)
{
if(pl==pr)
{
tree[p]=a[pl];
return ;
}
long long mid=(pl+pr)>>1;
build(p*2,pl,mid);
build(p*2+1,mid+1,pr);
update(p);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
build(1,1,n);
while(m--)
{
long long temp,x,y,k;
scanf("%lld",&temp);
if(temp==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
change(1,n,k,x,y,1);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",ask(1,n,x,y,1));
}
}
return 0;
} by zjr2014 @ 2024-11-07 20:28:20
@wangxinyu5483
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,c1[1000001],c2[1000001],x,op,l,r;
ll lowbit(ll x){
return x&-x;
}
void add(ll a[],ll i,ll x){
while(i<=n){
a[i]+=x;
i+=lowbit(i);
}
}
ll query(ll a[],ll i){
ll ans=0;
while(i){
ans+=a[i];
i-=lowbit(i);
}
return ans;
}
ll getsum(ll l,ll r){
return (r+1)*query(c1,r)-l*query(c1,l-1)-query(c2,r)+query(c2,l-1);
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>x;
add(c1,i+1,-x);
add(c1,i,x);
add(c2,i+1,-x*(i+1));
add(c2,i,x*i);
}
while(q-->0){
cin>>op>>l>>r;
if(op==1){
cin>>x;
add(c1,r+1,-x);
add(c1,l,x);
add(c2,r+1,-x*(r+1));
add(c2,l,x*l);
}
else{
cout<<getsum(l,r)<<"\n";
}
}
return 0;
}by wangxinyu5483 @ 2024-11-07 20:29:12
@zjr2014 我用的是线段树！！！！！！！！！！
by pig1121 @ 2024-11-07 20:43:44
@wangxinyu5483 修改也要 update
by wangxinyu5483 @ 2024-11-09 14:26:30
@pig1121 具体是哪里？？？我比较傻
by wangxinyu5483 @ 2024-11-09 14:27:09
@pig1121 是在change里面吗
by pig1121 @ 2024-11-10 07:20:19
@wangxinyu5483 是的，change 最后要 update 一次