/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "arbint.in" ;
const char OUT [ ] = "arbint.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

const int MAX = 1e5 + 14 ;

class SegmentTree {

public :
    vector < long long > Sum ;
    vector < long long > Tree ;
    vector < long long > Lazy ;
    SegmentTree ( ) {
        Sum.resize ( MAX << 2 ) ;
        Tree.resize ( MAX << 2 ) ;
        Lazy.resize ( MAX << 2 ) ;
    }
    void Reset ( )
    {
        fill ( Sum.begin ( ) , Sum.end ( ) , 0 ) ;
        fill ( Tree.begin ( ) , Tree.end ( ) , 0 ) ;
        fill ( Lazy.begin ( ) , Lazy.end ( ) , 0 ) ;
    }
    void Push ( int nod , int st , int dr , int level )
    {
        if ( level == 2 ) {
            return ;
        }
        if ( Lazy [ nod ] ) {
            Tree [ nod ] += Lazy [ nod ] ;
            Sum [ nod ] += Lazy [ nod ] * ( dr - st + 1 ) ;
            if ( st != dr ) {
                Lazy [ nod << 1 ] += Lazy [ nod ] ;
                Lazy [ nod << 1 | 1 ] += Lazy [ nod ] ;
            }
            Lazy [ nod ] = 0 ;
            int mij = ( st + dr ) >> 1 ;
            if ( st != dr ) {
                Push ( nod << 1 , st , mij , level + 1 ) ;
                Push ( nod << 1 | 1 , mij + 1 , dr , level + 1 ) ;
            }
        }
    }
    long long Acces ( int nod , int st , int dr , int pos )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( st == dr ) {
            return Tree [ nod ] ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( pos <= mij ) {
            return Acces ( nod << 1 , st , mij , pos ) ;
        }
        else {
            return Acces ( nod << 1 | 1 , mij + 1 , dr , pos ) ;
        }
        Tree [ nod ] = Tree [ nod << 1 ] + Tree [ nod << 1 | 1 ] ;
        Sum [ nod ] = Sum [ nod << 1 ] + Sum [ nod << 1 | 1 ] ;
    }
    void ElementUpdate ( int nod , int st , int dr , int pos , int val )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( st == dr ) {
            Tree [ nod ] = val ;
            Sum [ nod ] = val ;
            return ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( pos <= mij ) {
            ElementUpdate ( nod << 1 , st , mij , pos , val ) ;
        }
        else {
            ElementUpdate ( nod << 1 | 1 , mij + 1 , dr , pos , val ) ;
        }
        Tree [ nod ] = max ( Tree [ nod << 1 ] , Tree [ nod << 1 | 1 ] ) ;
        Sum [ nod ] = Sum [ nod << 1 ] + Sum [ nod << 1 | 1 ] ;
    }
    void RangeUpdate ( int nod , int st , int dr , int a , int b , long long Value )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            Lazy [ nod ] += Value ;
            return ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( a <= mij ) {
            RangeUpdate ( nod << 1 , st , mij , a , b , Value ) ;
        }
        if ( b > mij ) {
            RangeUpdate ( nod << 1 | 1 , mij + 1 , dr , a , b , Value ) ;
        }
        Tree [ nod ] = max ( Tree [ nod << 1 ] , Tree [ nod << 1 | 1 ] ) ;
        Sum [ nod ] = Sum [ nod << 1 ] + Sum [ nod << 1 | 1 ] ;
    }
    long long RangeQuery ( int nod , int st , int dr , int a , int b )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            return Tree [ nod ] ;
        }
        int mij = ( st + dr ) >> 1 ;
        long long LeftMaximum = 0 ;
        long long RightMaximum = 0 ;
        if ( a <= mij ) {
            LeftMaximum = RangeQuery ( nod << 1 , st , mij , a , b ) ;
        }
        if ( b > mij ) {
            RightMaximum = RangeQuery ( nod << 1 | 1 , mij + 1 , dr , a , b ) ;
        }
        Tree [ nod ] = max ( Tree [ nod << 1 ] , Tree [ nod << 1 | 1 ] ) ;
        Sum [ nod ] = Sum [ nod << 1 ] + Sum [ nod << 1 | 1 ] ;
        return max ( LeftMaximum , RightMaximum ) ;
    }
    long long RangeSumQuery ( int nod , int st , int dr , int a , int b )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            return Sum [ nod ] ;
        }
        int mij = ( st + dr ) >> 1 ;
        long long LeftSum = 0 ;
        long long RightSum = 0 ;
        if ( a <= mij ) {
            LeftSum = RangeSumQuery ( nod << 1 , st , mij , a , b ) ;
        }
        if ( b > mij ) {
            RightSum = RangeSumQuery ( nod << 1 | 1 , mij + 1 , dr , a , b ) ;
        }
        Tree [ nod ] = max ( Tree [ nod << 1 ] , Tree [ nod << 1 | 1 ] ) ;
        Sum [ nod ] = Sum [ nod << 1 ] + Sum [ nod << 1 | 1 ] ;
        return LeftSum + RightSum ;
    }

};

class PersistentSegmentTree
{
public :
    struct Tree {
        int leftt ;
        int rightt ;
        long long Sum ;
        long long Max ;
        long long Lazy ;
    };
    vector < int > Roots ;
    vector < Tree > Arb ;
    int nodes ;
    PersistentSegmentTree ( )
    {
        nodes = 0 ;
        Roots.resize ( MAX << 2 ) ;
        Arb.resize ( MAX << 2 ) ;
    }
    int copynode ( int nod )
    {
        ++ nodes ;
        Arb [ nodes ] = Arb [ nod ] ;
        return nodes ;
    }
    void resetP ( )
    {
        fill ( Roots.begin() , Roots.end() , 0 ) ;
        Arb.clear() ;
        nodes = 0 ;
    }
    void Push ( int nod , int st , int dr , int level )
    {
        if ( level == 2 ) {
            return ;
        }
        if ( Arb [ nod ].Lazy ) {
            Arb [ nod ].Max += Arb [ nod ].Lazy ;
            Arb [ nod ].Sum += Arb [ nod ].Lazy * ( dr - st + 1 ) ;
            if ( st != dr ) {
                int leftson = Arb [ nod ].leftt ;
                int rightson = Arb [ nod ].rightt ;
                Arb [ leftson ].Lazy += Arb [ nod ].Lazy ;
                Arb [ rightson ].Lazy += Arb [ nod ].Lazy ;
            }
            Arb [ nod ].Lazy = 0 ;
            int mij = ( st + dr ) >> 1 ;
            if ( st != dr ) {
                Push ( Arb [ nod ].leftt , st , mij , level + 1 ) ;
                Push ( Arb [ nod ].rightt , mij + 1 , dr , level + 1 ) ;
            }
        }
    }
    long long Acces ( int nod , int st , int dr , int pos )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( st == dr ) {
            return Arb [ nod ].Max ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( pos <= mij ) {
            return Acces ( Arb [ nod ].leftt , st , mij , pos ) ;
        }
        else {
            return Acces ( Arb [ nod ].rightt , mij + 1 , dr , pos ) ;
        }
        Arb [ nod ].Max = max ( Arb [ Arb [ nod ].leftt ].Max , Arb [ Arb [ nod ].rightt ].Max ) ;
        Arb [ nod ].Sum = Arb [ Arb [ nod ].leftt ].Sum + Arb [ Arb [ nod ].rightt ].Sum ;
    }
    int NewRootAfterUpdateonPosition ( int nod , int st , int dr , int pos , int val )
    {
        Push ( nod , st , dr , 0 ) ;
        nod = copynode ( nod ) ;
        if ( st == dr ) {
            Arb [ nod ].Max = val ;
            Arb [ nod ].Sum = val ;
            return nod ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( pos <= mij ) {
            Arb [ nod ].leftt = NewRootAfterUpdateonPosition ( Arb [ nod ].leftt , st , mij , pos , val ) ;
        }
        else {
            Arb [ nod ].rightt = NewRootAfterUpdateonPosition ( Arb [ nod ].rightt , mij + 1 , dr , pos , val ) ;
        }
        Arb [ nod ].Max = max ( Arb [ Arb [ nod ].leftt ].Max , Arb [ Arb [ nod ].rightt ].Max ) ;
        Arb [ nod ].Sum = Arb [ Arb [ nod ].leftt ].Sum + Arb [ Arb [ nod ].rightt ].Sum ;
        return nod ;
    }
    void RangeUpdate ( int nod , int st , int dr , int a , int b , long long Value )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            Arb [ nod ].Lazy += Value ;
            return ;
        }
        int mij = ( st + dr ) >> 1 ;
        if ( a <= mij ) {
            RangeUpdate ( Arb [ nod ].leftt , st , mij , a , b , Value ) ;
        }
        if ( b > mij ) {
            RangeUpdate ( Arb [ nod ].rightt , mij + 1 , dr , a , b , Value ) ;
        }
        Arb [ nod ].Max = max ( Arb [ Arb [ nod ].leftt ].Max , Arb [ Arb [ nod ].rightt ].Max ) ;
        Arb [ nod ].Sum = Arb [ Arb [ nod ].leftt ].Sum + Arb [ Arb [ nod ].rightt ].Sum ;
    }
    long long SumonCurrentInterval ( int nod , int st , int dr , int a , int b )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            return Arb [ nod ].Sum ;
        }
        int mij = ( st + dr ) >> 1 ;
        long long LeftSum = 0 ;
        long long RightSum = 0 ;
        if ( a <= mij ) {
            LeftSum = SumonCurrentInterval ( Arb [ nod ].leftt , st , mij , a , b ) ;
        }
        if ( b > mij ) {
            RightSum = SumonCurrentInterval ( Arb [ nod ].rightt , mij + 1 , dr , a , b ) ;
        }
        Arb [ nod ].Max = max ( Arb [ Arb [ nod ].leftt ].Max , Arb [ Arb [ nod ].rightt ].Max ) ;
        Arb [ nod ].Sum = Arb [ Arb [ nod ].leftt ].Sum + Arb [ Arb [ nod ].rightt ].Sum ;
        return LeftSum + RightSum ;
    }
    long long MaximumonCurrentInterval ( int nod , int st , int dr , int a , int b )
    {
        Push ( nod , st , dr , 0 ) ;
        if ( a <= st and dr <= b ) {
            return Arb [ nod ].Max ;
        }
        int mij = ( st + dr ) >> 1 ;
        long long LeftMaximum = 0 ;
        long long RightMaximum = 0 ;
        if ( a <= mij ) {
            LeftMaximum = MaximumonCurrentInterval ( Arb [ nod ].leftt , st , mij , a , b ) ;
        }
        if ( b > mij ) {
            RightMaximum = MaximumonCurrentInterval ( Arb [ nod ].rightt , mij + 1 , dr , a , b ) ;
        }
        Arb [ nod ].Max = max ( Arb [ Arb [ nod ].leftt ].Max , Arb [ Arb [ nod ].rightt ].Max ) ;
        Arb [ nod ].Sum = Arb [ Arb [ nod ].leftt ].Sum + Arb [ Arb [ nod ].rightt ].Sum ;
        return max ( LeftMaximum , RightMaximum ) ;
    }

};

int main ( void )
{
    int n , m ;
    cin >> n >> m ;
    SegmentTree Arbore ;
    Arbore.Reset() ;
    PersistentSegmentTree Copac ;
    Copac.resetP() ;
    FORN ( i , 1 , n ) {
        int Value ;
        cin >> Value ;
        Arbore.ElementUpdate ( 1 , 1 , n , i , Value ) ;
    }
    /***FORN ( i , 1 , n ) {
        cout << Arbore.Acces ( 1 , 1 , n , i ) << ' ' ;
    }
    cout << '\n' ;
    FORN ( len , 1 , n ) {
        cout << "sumele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " suma este " << Arbore.RangeSumQuery ( 1 , 1 , n , i , j ) << '\n' ;
        }
    }
    cout << '\n' ;
    FORN ( len , 1 , n ) {
        cout << "maximele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " maximul este " << Arbore.RangeQuery ( 1 , 1 , n , i , j ) << '\n' ;
        }
    }
    Arbore.RangeUpdate ( 1 , 1 , n , 1 , n , 1 ) ;
    //FORN ( i , 1 , n ) {
    //    cout << Arbore.Acces ( 1 , 1 , n , i ) << ' ' ;
    //}
    cout << '\n' ;
    FORNBACK ( len , n , 1 ) {
        cout << "sumele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " suma este " << Arbore.RangeSumQuery ( 1 , 1 , n , i , j ) << '\n' ;
        }
    }
    cout << '\n' ;
    FORNBACK ( len , n , 1 ) {
        cout << "maximele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " maximul este " << Arbore.RangeQuery ( 1 , 1 , n , i , j ) << '\n' ;
        }
    }
    return 0 ;***/
    while ( m -- ) {
        int Type ;
        cin >> Type ;
        if ( not Type ) {
            int _Left , _Right ;
            cin >> _Left >> _Right ;
            cout << Arbore.RangeQuery ( 1 , 1 , n , _Left , _Right ) << '\n' ;
        }
        else {
            int Position , Value ;
            cin >> Position >> Value ;
            Arbore.ElementUpdate ( 1 , 1 , n , Position , Value ) ;
        }
    }
    /***
    FORN ( i , 1 , n ) {
        int Value ;
        cin >> Value ;
        Copac.Roots [ i ] = Copac.NewRootAfterUpdateonPosition ( Copac.Roots [ i - 1 ] , 1 , n , i , Value ) ;
    }***/
    //FORN ( i , 1 , n ) {
    //    cout << Copac.Acces ( Copac.Roots [ n ] , 1 , n , i ) << ' ' ;
    //}
    //cout << '\n' ;
    //Copac.RangeUpdate ( Copac.Roots [ n ] , 1 , n , 1 , n , 1 ) ;
    //FORN ( i , 1 , n ) {
    //    cout << Copac.Acces ( Copac.Roots [ n ] , 1 , n , i ) << ' ' ;
    //}
    /*cout << '\n' ;
    FORNBACK ( len , n , 1 ) {
        cout << "sumele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " suma este " << Copac.SumonCurrentInterval( Copac.Roots [ n ] , 1 , n , i , j ) << '\n' ;
        }
    }
    cout << '\n' ;
    FORNBACK ( len , n , 1 ) {
        cout << "maximele pe intervalele de lungime " << len << " sunt \n" ;
        FORN ( i , 1 , n ) {
            int j = i + len - 1 ;
            if ( j > n ) {
                break ;
            }
            cout << "pe intervalul " << i << ' ' << j << " maximul este " << Copac.MaximumonCurrentInterval ( Copac.Roots [ n ] , 1 , n , i , j ) << '\n' ;
        }
    }*/
    return 0;
}