玄关求助

为什么线段树会超时啊...哭死，还没暴力得分多 有没有大佬帮忙看看

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e6 + 7;
int n, m;
struct node{
    int sum, val, ls, rs;
}w[maxn<<2];
void pushup(int u){
    int l = u * 2;
    int r = u * 2 + 1;
    w[u].sum = w[l].sum + w[r].sum;
    w[u].ls = max(w[l].sum + w[r].ls, w[l].ls);
    w[u].rs = max(w[r].rs, w[l].rs + w[r].sum);
    w[u].val = max(max(w[l].val, w[r].val), w[l].rs + w[r].ls);
}
void build(int u, int l, int r){
    if(l == r){
        int a;
        scanf("%d", &a);
        w[u].sum = w[u].val = w[u].ls = w[u].rs = a;
        //w[u].val = a[l];
        //w[u].ls = a[l];
        //w[u].rs = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(u * 2, l, mid);
    build(u*2+1, mid+1, r);
    pushup(u);
}
void maketag(int u, int x){
    w[u].sum = w[u].val = w[u].ls = w[u].rs = x;
}
void update(int u, int l, int r, int ql, int x){
    if(l == r) {
        maketag(u, x);
        return;
    }
    int mid = l + r >> 1;
    if(ql <= mid)
        update(u*2, l, mid, ql, x);
    else
        update(u*2+1, mid+1, r, ql, x);
    pushup(u);
}
node qry(int u, int l, int r, int ql, int qr){
    if(l == r)
        return w[u];
    int mid = l + r >> 1;
    if(qr <= mid)
        return qry(u*2, l, mid, ql, qr);
    if(ql > mid){
        return qry(u*2+1, mid+1, r, ql, qr);
    }
    node z, x = qry(u*2, l, mid, ql, qr), y = qry(u*2+1, mid+1, r, ql, qr);
    z.sum = x.sum + y.sum;
    z.val = max(max(x.val, y.val), x.rs + y.ls);
    z.ls = max(x.sum + y.ls, x.ls);
    z.rs = max(y.sum + x.rs, y.rs);
    return z;
}
int main(){
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for(int i=1;i<=m;i++){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op==1){
            if(x > y)
                swap(x, y);
            printf("%d\n", qry(1, 1, n, x, y).val);
        }
        else {
            update(1, 1, n, x, y);
        }
    }
    return 0;
}