@[2661531273zwm](/space/show?uid=161999) ~~没必要每个数组都开四倍吧吧吧~~你是全wa吗?
by xlxl @ 2019-08-13 14:29:45
@[2661531273zwm](/space/show?uid=161999) 只有建树的时候传边是传(l,mid,p*2)(mid+1,r,p**2+1),其它都是传(l,r,p*2)(l,r,p**2+1)..一个乘号打不出来,
你再看一下线段树模板吧
by xlxl @ 2019-08-13 14:36:39
@[xlxl](/space/show?uid=120669)
这是我的线段树模板,好像没什么区别啊。。。
```cpp
#include<bits/stdc++.h>
using namespace std;
# define maxn 1000001
# define ll long long
unsigned ll n,m,a[maxn],tag[maxn<<2],ans[maxn<<2];
void scan()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
}
inline int ls(ll p) {return p<<1;}
inline int rs(ll p) {return p<<1|1;}
void push_up_sum(ll p) {ans[p]=ans[ls(p)]+ans[rs(p)];}
void build(ll p,ll l,ll r)
{
tag[p]=0;
if(l==r)
{
ans[p]=a[l]; return;
}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up_sum(p);
}
inline void f(ll p,ll l,ll r,ll k)
{
tag[p]=tag[p]+k;
ans[p]=ans[p]+k*(r-l+1);
}
inline void push_down(ll p,ll l,ll r)
{
ll mid=(l+r)>>1;
f(ls(p),l,mid,tag[p]);
f(rs(p),mid+1,r,tag[p]);
tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l&&nr>=r)
{
ans[p]+=k*(r-l+1);
tag[p]+=k;
return;
}
push_down(p,l,r);
ll mid =(l+r)>>1;
if(nl<=mid) update(nl,nr,l,mid,ls(p),k);
if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
push_up_sum(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
ll res=0;
if(q_x<=l&&q_y>=r)
{
return ans[p];
}
ll mid=(l+r)>>1;
push_down(p,l,r);
if(q_x<=mid) res+=query(q_x,q_y,l,mid,ls(p));
if(q_y>mid) res+=query(q_x,q_y,mid+1,r,rs(p));
return res;
}
int main()
{
ll a1,b,c,d,e,f;
scan();
build(1,1,n);
while(m--)
{
scanf("%lld",&a1);
switch(a1)
{
case 1:
{
cin>>b>>c>>d;
update(b,c,1,n,1,d);
break;
}
case 2:
{
cin>>e>>f;
cout<<query(e,f,1,n,1)<<endl;
break;
}
}
}
return 0;
}
```
by 2661531273zwm @ 2019-08-13 15:38:51
@[2661531273zwm](/space/show?uid=161999) 我们不一样~~
我线段树模板长这样
```
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000010],m,x,y,ans,QWQ;
struct tree{
long long l,r,sum,add;
}t[1000010];
void build_tree(long long p,long long l,long long r){
t[p].l=l;
t[p].r=r;
t[p].add=0;
if(l==r){
t[p].sum=a[l];
return ;
}
long long mid=(l+r)/2;
build_tree(p*2,l,mid);
build_tree(p*2+1,mid+1,r);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void cbj(long long k){
if(t[k].add){
t[k*2].add+=t[k].add;
t[k*2+1].add+=t[k].add;
t[k*2].sum+=t[k].add*(t[k*2].r-t[k*2].l+1);
t[k*2+1].sum+=t[k].add*(t[k*2+1].r-t[k*2+1].l+1);
t[k].add=0;
}
}
void gg(long long l,long long r,long long d,long long p){
if(t[p].l>=l&&t[p].r<=r){
t[p].sum+=d*(t[p].r-t[p].l+1);
t[p].add+=d;
return ;
}
cbj(p);
long long mid=(t[p].l+t[p].r)/2;
if(l<=mid)
gg(l,r,d,p*2);
if(r>mid)
gg(l,r,d,p*2+1);
t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
long long cx(long long l,long long r,long long p){
if(l<=t[p].l&&r>=t[p].r){
return t[p].sum;
}
cbj(p);
long long mid=(t[p].l+t[p].r)/2;
long long sum=0;
if(l<=mid)
sum+=cx(l,r,p*2);
if(r>mid)
sum+=cx(l,r,p*2+1);
return sum;
}
int main(){
// freopen("easy.in","r",stdin);
// freopen("easy.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
build_tree(1,1,n);
for(long long i=1;i<=m;i++){
cin>>ans>>x>>y;
if(ans==1){
cin>>QWQ;
gg(x,y,QWQ,1);
}
else
cout<<cx(x,y,1)<<endl;
}
return 0;
}
```
by xlxl @ 2019-08-13 15:44:35
qwq
by 2661531273zwm @ 2019-08-13 15:53:10
@[xlxl](/space/show?uid=120669)
但是我的模板也没问题啊。。。
还有什么错吗
by 2661531273zwm @ 2019-08-13 15:53:58
@[2661531273zwm](/space/show?uid=161999) 溜了。。。溜了。。。。
by xlxl @ 2019-08-13 15:59:25
@[xlxl](/space/show?uid=120669)
感谢了
by 2661531273zwm @ 2019-08-13 16:03:06