29-算法训练 结点选择-超时了！！！

import java.util.Scanner;

public class Main {
	public static node[] t = new node[400000];
	public static long n, m, ans = 0, Max = -0x3f3f3f3f;
	public static Scanner cin = new Scanner(System.in);
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n = cin.nextLong();
		m = cin.nextLong();
	    build(1, n, 1);
	    while(m-- != 0){
	        int i, x, y;
	        Max = -0x3f3f3f3f;  //每次都要初始化
	        ans = 0;
	        i = cin.nextInt();
	        x = cin.nextInt();
	        y = cin.nextInt();
	        if(i == 1){
	            update(x, y, 1);
	        }
	        else if(i == 2){
	            query(x, y, 1);
//	            cout << ans << endl;
	            System.out.println(ans);
	        }
	        else if(i == 3){
	            query(x, y, 1);
//	            cout << Max << endl;
	            System.out.println(Max);
	        }
	    }
		
	}
	
	static void build(long l, long r, int k){
		t[k] = new node(); // 因为是对象数组，所以必须要new出对象，才能用
	    t[k].l = l;
	    t[k].r = r;
	    if(l == r){
//	        cin >> t[k].v;
	    	t[k].v = cin.nextLong();
	    	t[k].s = t[k].v;
	        return ;           //每个查找完都要结束
	    }
	    long mid = (l + r) / 2;
	    build(l, mid, k * 2);
	    build(mid + 1, r, k * 2 + 1);
	    t[k].v = Math.max(t[k * 2].v, t[k * 2 + 1].v);
	    t[k].s = t[k * 2].s + t[k * 2 + 1].s;
	}
	 
	static void update(int c, int v, int k){
	    if(t[k].l == t[k].r && t[k].l == c){
	        t[k].v = v;
	        t[k].s = v;   //这个也要改才行哇！！！
	        return ;  //每个查找玩，都要结束　　
	    }
	    long mid = (t[k].l + t[k].r) / 2;
	    if(c <= mid){
	        update(c, v, k * 2);
	    }
	    else{
	        update(c, v, k * 2 + 1);
	    }
	    t[k].v = Math.max(t[k * 2].v, t[k * 2 + 1].v);
	    t[k].s = t[k * 2].s + t[k * 2 + 1].s;
	}
	 
	static void query(long l, long mid2, int k){
	    if(t[k].r < l || t[k].l > mid2){
	        return ;
	    }
	    if(l <= t[k].l && mid2 >= t[k].r){
	        ans += t[k].s;
	        if(Max < t[k].v){
	            Max = t[k].v;
	        }
	        return ;    //查找玩要立即结束
	    }
	    long mid = (t[k].l + t[k].r) / 2; //这里是节点的区间中点
	    if(mid > mid2){
	        query(l, mid2, k * 2);
	    }
	    else if(mid < l){
	        query(l, mid2, k * 2 + 1);
	    }
	    else{
	        query(l, mid, k * 2);
	        query(mid + 1, mid2, k * 2 + 1);
	    }
	}
	
}
class node{
	public long l;
	public long r;
	public long v, s;
}