Ленивое распространение — УЖАСНЫЕ спой

Я пытаюсь решить проблему УЖАСНО из спой, и вот ссылка: http://www.spoj.com/problems/HORRIBLE/ Я пытаюсь научить себя ленивому распространению с помощью дерева сегментов. Ниже приведен код, который я написал, я постарался сделать его максимально лаконичным и понятным, пожалуйста, дайте мне знать, если что-то неясно.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

ll tree[500010];
ll lazy[500010]={};

void buildST(ll A[], ll STidx, ll l, ll r)
{
if(l==r)
{
tree[STidx]=A[l];
return;
}
ll left=2*STidx, right=left+1, mid=(l+r)/2;
buildST(A, left, l, mid);
buildST(A, right, mid+1, r);
tree[STidx]=tree[left]+tree[right];
}

void update(ll STidx, ll i, ll j, ll l, ll r, ll val)
{
//printf("%lld %lld %lld %lld %lld\n", STidx, i, j, l, r);
if(lazy[STidx]!=0)
{
tree[STidx]+=(l-r+1)*lazy[STidx];
if(l!=r)
{
lazy[2*STidx]+=lazy[STidx];
lazy[2*STidx+1]+=lazy[STidx];
}
lazy[STidx]=0;
}
//printf("1\n");
if(l>r || l>j || r<i)
return;
//printf("1\n");
if(l>=i && r<=j)
{
//printf("%lld\n", STidx);
tree[STidx]+=(r-l+1)*val;
if(l!=r)
{
lazy[2*STidx]+=val;
lazy[2*STidx+1]+=val;
}
return;
}
ll mid=(l+r)/2;
update(2*STidx, i, j, l, mid, val);
update(2*STidx+1, i, j, mid+1, r, val);
tree[STidx]=tree[2*STidx]+tree[2*STidx+1];
}

ll query(ll STidx, ll i, ll j, ll l, ll r)
{
if(lazy[STidx]!=0)
{
tree[STidx]+=lazy[STidx]*(r-l+1);
if(l!=r)
{
lazy[2*STidx]+=lazy[STidx];
lazy[2*STidx+1]+=lazy[STidx];
}
lazy[STidx]=0;
}
if(l>r || l>j || r<i)
return 0;
if(l>=i && r<=j)
return tree[STidx];
ll mid=(l+r)/2;
ll q1=query(2*STidx, i, j, l, mid);
ll q2=query(2*STidx+1, i, j, mid+1, r);
return q1+q2;
}

ll A[100010];

int main()
{
ll T, N, C, type, p, q, v, i;
scanf("%lld", &T);
while(T--)
{
scanf(" %lld %lld", &N, &C);
for(i=0; i<N; ++i)
A[i]=0;
for(i=0; i<4*N; ++i)
lazy[i]=0;
buildST(A, 1, 0, N-1);
while(C--)
{
scanf(" %lld", &type);
if(type==0)
{
scanf(" %lld %lld %lld", &p, &q, &v);
update(1, p-1, q-1, 0, N-1, v);
//for(i=1; i<=15; ++i)
//  printf("%lld ", tree[i]);
//printf("\n");
}
if(type==1)
{
scanf(" %lld %lld", &p, &q);
printf("%lld\n", query(1, p-1, q-1, 0, N-1));
}
}
}
return 0;
}

Приведенный пример тестового примера дает правильный ответ с моим кодом, но при отправке я получаю неправильное ответное сообщение. Я проверял свой код много раз, но не могу найти ошибку.

Любая помощь приветствуется. Спасибо!