TLE求调

线段树做法，有懒标记，TLE了最后三个点，是时间复杂度错了还是做法有误？

评测记录

#include<bits/stdc++.h>
using namespace std;
#define lson p << 1
#define rson p << 1 | 1
#define mid (l + r >> 1)
const int N = 1e5 + 5;
struct node {
    long long val,lazy;
    node():val(0){};
    node(int x):val(x){};
    friend node operator + (const node &l,const node &r) {//运算
        return l.val + r.val;
    }
}tr[N << 2];
int s[N];
void spread(int p,int l,int r,long long tag) {
    tr[p].lazy += tag;
    tr[p].val += tag * (r - l + 1);
    return ;
}
void push_down(int p,int l,int r) {
    if(tr[p].lazy && l != r) {
        spread(lson,l,mid,tr[p].lazy);
        spread(rson,mid + 1,r,tr[p].lazy);
        tr[p].lazy = 0;
    }
}
void build(int p,int l,int r) {
    if(l == r) {
        tr[p] = node(s[l]);
    }
    else {
        build(lson,l,mid);
        build(rson,mid + 1,r);
        tr[p] = tr[lson] + tr[rson];
    }
}
void change(int p,int l,int r,int ql,int qr,long long val) {//修改 
    if(l == r) {
        spread(p,l,r,val);
    }
    else {
        push_down(p,l,r); 
        if(ql <= mid) {
            change(lson,l,mid,ql,qr,val);
        }
        if(qr > mid) {
            change(rson,mid + 1,r,ql,qr,val);
        }
        tr[p] = tr[lson] + tr[rson];
    }
}
node query(int p,int l,int r,int ql,int qr) {//查询 
    if(ql <= l && r <= qr) {
        return tr[p];
    }
    node ans = node();
    push_down(p,l,r);
    if(ql <= mid) {
        ans = ans + query(lson,l,mid,ql,qr);
    }
    if(qr > mid) {
        ans = ans + query(rson,mid + 1,r,ql,qr);
    }
    return ans;
}
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&s[i]);
    }
    build(1,1,n);
    for(int i = 1;i <= q;i ++) {
        int op;
        scanf("%d",&op);
        if(op == 1) {
            int l,r;
            long long val;
            scanf("%d%d%d",&l,&r,&val);
            change(1,1,n,l,r,val);
        }
        else {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",query(1,1,n,l,r).val);
        }
    }
    return 0;
}