关于空间

为什么我这份代码的空间不够会RE，数组开大一点就A了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+9;
ll a[maxn],tree[maxn*4],lazy[maxn*4];//tree存储某个节点区间和 
int n,m;
void build(int l,int r,int fa)//fa表示当前结点的下标 
{
    int mid=(l+r)/2;
    if(l==r)  
    {
        tree[fa]=a[mid];
        return ;
    }
    build(l,mid,fa*2);
    build(mid+1,r,fa*2+1);
    tree[fa]=tree[fa*2]+tree[fa*2+1];
}
ll search(int x,int y,int fa,int l,int r)
{
    int mid=(l+r)/2;
    if(lazy[fa]&&l!=r)
    {
        tree[fa*2]+=(mid-l+1)*lazy[fa];
        tree[fa*2+1]+=(r-mid)*lazy[fa];
        tree[fa]=tree[fa*2]+tree[fa*2+1];
        lazy[fa*2]+=lazy[fa];
        lazy[fa*2+1]+=lazy[fa];
        lazy[fa]=0;
    }
    if(x<=l&&y>=r)
    {
        return tree[fa];
    }
    if(x>=mid+1)
    {
        return search(x,y,fa*2+1,mid+1,r);  
    } 
    else if(y<=mid)
    {
        return search(x,y,fa*2,l,mid);
    }
    else
    {
        return search(x,y,fa*2,l,mid)+search(x,y,fa*2+1,mid+1,r);
    }
}
void change(int x,int y,int fa,int l,int r,ll k)
{   
    int mid=(l+r)/2;
    if(lazy[fa])
    {
        tree[fa*2]+=(mid-l+1)*lazy[fa];
        tree[fa*2+1]+=(r-mid)*lazy[fa];
        lazy[fa*2]+=lazy[fa];
        lazy[fa*2+1]+=lazy[fa];
        lazy[fa]=0;
    }

    if(x<=l&&y>=r)
    {
        lazy[fa]+=k; 
        tree[fa]+=(r-l+1)*k;
        return ;
    }

    if(x>=mid+1)
    {
        //cout<<"???????";
        change(x,y,fa*2+1,mid+1,r,k);

    } 
    else if(y<=mid)
    {
        //cout<<"\\\\\\";   
        change(x,y,fa*2,l,mid,k);       
    }
    else
    {
        //cout<<":::::";
        change(x,y,fa*2,l,mid,k);
        change(x,y,fa*2+1,mid+1,r,k);   
    }
    tree[fa]=tree[fa*2]+tree[fa*2+1];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
//  int i=1;
//  while(tree[i++])
//  {
//      cout<<tree[i-1]<<" ";
//  }
    while(m--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int x,y;
            ll k;
            scanf("%d %d %lld",&x,&y,&k);
            change(x,y,1,1,n,k);
//          for(int i=1;i<=4*n;i++)
//          {
//              cout<<tree[i]<<" ";
//          }
        //  cout<<"\n";
        }
        else
        {
            int x,y;
            scanf("%d %d",&x,&y);
            printf("%lld\n",search(x,y,1,1,n)); 
        }
    } 
}