SPOJ -> HORRIBLE - Horrible Queries

// using sqrt decomposition

#include<bits/stdc++.h>
using namespace std;
int main(){
                       int t;
                       scanf("%d",&t);
                       while(t--){
    long long n , q , ch , l , r ,v,t1,t2 ,i ;
         scanf("%lld%lld",&n,&q);
           long long  arr[n+1];
      memset(arr,0,sizeof arr);
      //  for(int i  = 0 ; i < n ; ++i )
        //   scanf("%lld",&arr[i]);
        long long val = sqrt(n);
        long long sz = (n-1)/val;
        long long sq[sz+1][3];
        memset(sq,0,sizeof sq);
       // for( i = 0; i < n ; ++i )
         //   sq[i/val][1]=(sq[i/val][1]+arr[i])%mod;
               while(q--)
               {
                    scanf("%lld%lld%lld",&ch,&l,&r);
                   l--;
                    r--;
                      if(ch == 0)
                      {
                          scanf("%lld",&v );
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                          {
                                arr[i] = (arr[i] + v);
                                sq[t1][1] = (sq[t1][1]+v);
                          }
                          for( i = t1+1 ; i < t2 ; ++i )
                              sq[i][2] = (sq[i][2] + v);
                              if(t1 != t2 )
                              for(int i = r ; i/val==t2 && i>=l; --i )
                              {
                                  arr[i] = (arr[i] + v);
                                  sq[t2][1] = (sq[t2][1]+v);
                              }
                                        }
                      else
                      {
                          long long ans = 0;
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                              ans = (ans + (arr[i] + sq[t1][2]));
                          for( i = t1+1 ; i < t2 ; ++i )
                            ans = (ans + (sq[i][1]+(sq[i][2]*val)));
                               if(t1 != t2 )
                              for( i = r ; i/val==t2 && i>=l; --i )
                              ans = (ans + (arr[i] + sq[t2][2]));
                              printf("%lld\n",ans);
                      }

               }
                       }
           return 0;
}