解析：

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    static int[] w;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        tr = new Node[n * 4];
        w = new int[n + 1];
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++) w[i] = Integer.valueOf(ss[i - 1]);

        buildTree(1, 1, n);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            switch(ss[0]){
                case "1":
                    int l = Integer.valueOf(ss[1]), r = Integer.valueOf(ss[2]);
                    if(l > r)    {int tmp = l; l = r; r = tmp;}
                    log.write(query(1, l, r).tmax + "\n");
                    break;
                case "2":
                    int x = Integer.valueOf(ss[1]), c = Integer.valueOf(ss[2]);
                    modify(1, x, c);
                    break;
            }
        }
        log.flush();
    }


    public static Node query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u];
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l , r);
        {
            Node n1 = query(u << 1, l, r);
            Node n2 = query(u << 1 | 1, l, r);
            Node res = new Node(l, r);
            pushUp(res, n1, n2);
            return res;
        }
    }

    public static void modify(int u, int x, int c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].tmax = c; tr[u].lmax = c; tr[u].rmax = c; tr[u].sum = c;
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void buildTree(int u, int l, int r){
        if(l == r){
            tr[u] = new Node(l, r, w[l], w[l], w[l], w[l]);
        }else{
            tr[u] = new Node(l, r);
            int mid = l + r >> 1;
            buildTree(u << 1, l, mid); buildTree(u << 1 | 1, mid + 1, r);
            pushUp(u);
        }

    }

    public static void pushUp(int u){
        pushUp(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }

    public static void pushUp(Node u, Node l, Node r){
        u.sum = l.sum + r.sum;
        u.lmax = Math.max(l.lmax, l.sum + r.lmax);
        u.rmax = Math.max(r.rmax, l.rmax + r.sum);
        u.tmax = Math.max(Math.max(l.tmax, r.tmax), l.rmax + r.lmax);
    }

    static class Node{
        int l, r;
        int tmax, lmax, rmax, sum;
        Node(int l, int r, int tmax, int lmax, int rmax, int sum){
            this.l = l; this.r = r; this.tmax = tmax; this.lmax = lmax;
            this.rmax = rmax; this.sum = sum;
        }
        Node(int l, int r){
            this.l = l; this.r = r;
        }
    }
}