求助卡空间，#9 MLE

#include <bits/stdc++.h>
using namespace std;

inline int Read() {
  int x = 0 , f = 1;
  char c = getchar();
  for( ; c < '0' || c > '9' ; c = getchar() ) f ^= ( c == '-' );
  for( ; c >= '0' && c <= '9' ; c = getchar() ) x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 );
  return f ? x : -x;
}

struct SMT {
private:
  struct Node {
    Node *L , *R;
    int l , r;
    int sum , pre , suf , ans;
    Node( int l , int r ) : l(l),r(r),L(NULL),R(NULL),sum(0),pre(0),suf(0),ans(0) {}
    int mid() { return l + ( r - l ) / 2 ; }
    int len() { return r - l + 1 ; }
    void PushUp() {
      sum = L->sum + R->sum;
      pre = max( L->pre , L->sum + R->pre );
      suf = max( R->suf , L->suf + R->sum );
      ans = max( max( L->ans , R->ans ) , max( max( suf , pre ) , L->suf + R->pre ) );
    }
  };
public:
  Node *root;
  void Build( int l , int r , Node *&p , int a[] ) {
    p = new Node( l , r );
    if( l == r ) {
      p->sum = p->pre = p->suf = p->ans = a[ l ];
      return;
    }
    Build( l , p->mid() , p->L , a ) , Build( p->mid() + 1 , r , p->R , a );
    p->PushUp();
  }
  void Update( int x , int v , Node *p ) {
    if( p->l == x && x == p->r ) {
      p->sum = p->pre = p->suf = p->ans = v;
      return;
    }
    if( x <= p->mid() ) Update( x , v , p->L );
    if( x > p->mid() ) Update( x , v , p->R );
    p->PushUp();
  }
  Node *Query( int x , int y , Node *p ) {
    if( x <= p->l && p->r <= y ) return p;
    Node *res = new Node( x , y );
    if( y <= p->mid() ) return Query( x , y , p->L );
    if( p->mid() < x ) return Query( x , y , p->R );
    Node *left = Query( x , y , p->L ) , *right = Query( x , y , p->R );
    res->sum = left->sum + right->sum;
    res->pre = max( left->pre , left->sum + right->pre );
    res->suf = max( right->suf , right->sum + left->suf );
    res->ans = max( max( left->ans , right->ans ) , max( max( res->pre , res->suf ) , left->suf + right->pre ) );
    return res;
  }
} seg;

const int _ = 5e5 + 5;

int n , m;
int a[_];

int main() {
  n = Read() , m = Read();
  for( int i = 1 ; i <= n ; i++ ) {
    a[ i ] = Read();
  }
  seg.Build( 1 , n , seg.root , a );
  while( m-- ) {
    int op = Read() , x = Read() , y = Read();
    if( op == 1 ) {
      if( x > y ) swap( x , y );
      printf( "%d\n" , seg.Query( x , y , seg.root )->ans );
    } else {
      seg.Update( x , y , seg.root );
    }
  }
  return 0;
}