TLE

#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
lld a[100005];
struct var
{
    int l,r;
    lld val;
    var(){}
};var A[400005];
void buildTree(int id,int x,int y)
{
    A[id].l=x;A[id].r=y;
    if(x==y)
    {
        A[id].val=a[x];
        return;
    }
    int mid=(x+y)>>1;
    buildTree(id<<1,x,mid);
    buildTree(id<<1|1,mid+1,y);
    A[id].val=A[id<<1].val+A[id<<1|1].val;
}
void update(int id,int pos,lld value)
{
    int L=A[id].l,R=A[id].r;
    if(L==R and L==pos)
    {
        A[id].val+=value;
        return;
    }
    if(L<=pos and pos<=R)
    {
        update(id<<1,pos,value);
        update(id<<1|1,pos,value);
        A[id].val=A[id<<1].val+A[id<<1|1].val;
    }
}
lld ask(int id,int x,int y)
{
    int L=A[id].l,R=A[id].r;
    if(x<=L and R<=y)
        return A[id].val;
    int mid=(L+R)>>1;lld ans=0;
    if(x<=mid)ans+=ask(id<<1,x,y);
    if(mid<y)ans+=ask(id<<1|1,x,y);
    return ans;
}
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    buildTree(1,1,n);
    while(m--)
    {
        char op;cin>>op;
        if(op=='2')
        {
            int x,y;cin>>x>>y;
            cout<<ask(1,x,y)<<endl;
        }
        else if(op=='1')
        {
            int x,y,z;cin>>x>>y>>z;
            for(int i=x;i<=y;++i)
                update(1,i,z);
        }
    }
}