#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <algorithm> using namespace std; typedef long long llint; #define INF 0x3f3f3f3f #define MAXN 50005 struct Node { int q, lsum, rsum, sum; } node[4*MAXN]; void Update ( int v, int x, int y, int pos, int val ) { int mid = (x+y)/2; if ( x == y ) { node[v].q = node[v].lsum = node[v].rsum = node[v].sum = val; return; } if ( pos <= mid ) { Update ( 2*v, x, mid, pos, val ); } else { Update ( 2*v+1, mid+1, y, pos, val ); } node[v].q = max ( max ( node[2*v].q, node[2*v+1].q ), node[2*v].rsum + node[2*v+1].lsum ); node[v].sum = node[2*v].sum + node[2*v+1].sum; node[v].lsum = max ( node[2*v].lsum, node[2*v].sum + node[2*v+1].lsum ); node[v].rsum = max ( node[2*v+1].rsum, node[2*v+1].sum + node[2*v].rsum ); } Node Query ( int v, int x, int y, int Qx, int Qy ) { int mid = (x+y)/2; if ( x==Qx && y==Qy ) { return node[v]; } if ( Qy <= mid ) { return ( Query ( 2*v, x, mid, Qx, Qy ) ); } if ( Qx > mid ) { return ( Query ( 2*v+1, mid+1, y, Qx, Qy ) ); } Node o1, o2, o3; o1 = Query ( 2*v, x, mid, Qx, mid ); o2 = Query ( 2*v+1, mid+1, y, mid+1, Qy ); o3.q = max ( max ( o1.q, o2.q ), o1.rsum + o2.lsum ); o3.lsum = max ( o1.lsum, o1.sum + o2.lsum ); o3.rsum = max ( o2.rsum, o2.sum + o1.rsum ); o3.sum = o1.sum + o2.sum; return o3; } int main ( void ) { //freopen (".in","r",stdin); freopen(".out","w",stdout); int i, tmp, tmp1, tmp2, N, M; scanf ("%d", &N); for ( i=1; i<=N; ++i ) { scanf ("%d", &tmp); Update ( 1, 1, N, i, tmp ); } scanf ("%d", &M); for ( i=1; i<=M; ++i ) { scanf ("%d %d %d", &tmp, &tmp1, &tmp2 ); if ( tmp == 0 ) { Update ( 1, 1, N, tmp1, tmp2 ); } else { printf ("%d\n",( Query ( 1, 1, N, tmp1, tmp2 ) ).q ); } } return (0); }