ZJ d799: 区间求和 線段樹模板

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=d799

就線段樹模板

記得存值的變數要開大一點,例如long long

因為開太小吃WA

以下為code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0);

struct node

{

unsigned int l,r;

unsigned long long sum,lazy;

void update(unsigned long long x)

{

sum+=(r-l+1)*x;

lazy+=x;

}

} st[500001*4];

void push_up(unsigned int x)

{

st[x].sum=st[x<<1].sum+st[x<<1|1].sum;

}

void push_down(unsigned int x)

{

unsigned int lazy=st[x].lazy;

st[x<<1].update(lazy),st[x<<1|1].update(lazy);

st[x].lazy=0;

}

void build(unsigned int x,unsigned int l,unsigned int r)

{

st[x].l=l,st[x].r=r,st[x].sum=st[x].lazy=0;

if(l==r) cin>>st[x].sum;

else

{

unsigned int mid=(r+l)>>1;

build(x<<1,l,mid);

build(x<<1|1,mid+1,r);

push_up(x);

}

}

void modify(unsigned int x,unsigned int l,unsigned int r,unsigned long long num)

{

unsigned int L=st[x].l,R=st[x].r;

if(L>=l&&R<=r) st[x].update(num);

else

{

push_down(x);

unsigned int mid=(R+L)>>1;

if(l<=mid) modify(x<<1,l,r,num);

if(r>mid) modify(x<<1|1,l,r,num);

push_up(x);

}

}

unsigned long long query(unsigned int x,unsigned int l,unsigned int r)

{

unsigned int L=st[x].l,R=st[x].r;

if(L>=l&&R<=r) return st[x].sum;

else

{

push_down(x);

unsigned int mid=(R+L)>>1;

unsigned long long ans=0;

if(l<=mid) ans+=query(x<<1,l,r);

if(r>mid) ans+=query(x<<1|1,l,r);

push_up(x);

return ans;

}

}

int main()

{

AC

unsigned int n;

cin>>n;

build(1,1,n);

unsigned int q;

cin>>q;

while(q--)

{

unsigned int v,x,y,k;

cin>>v;

if(v==1) cin>>x>>y>>k,modify(1,x,y,k);

else if(v==2) cin>>x>>y,cout<<query(1,x,y)<<'\n';

}

}