Java :

import java.util.Scanner;

public class Main {
    int n,m;
    int[] A;                //存放学生的成绩

    public Main(){
        Scanner sc=new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        A = new int[n + 1];
        for (int i = 1; i <= n; i++) A[i] = sc.nextInt();   //读入数据
        BTNode root=Build(1,n);

        for (int i = 0; i < m; i++) {
            int oper = sc.nextInt();
            int x = sc.nextInt(), y = sc.nextInt();
            if (oper==1) {
            	A[x] = y;   Update(root,x,y);//更新操作
            }
            else if(oper==3)        //求连续一段格子的最大值
                  System.out.println(QueryMax(root,x,y));
            else  System.out.println(QuerySum(root,x,y));
        }
    }
    BTNode Build(int L, int R){       //键线段树的递归函数
        BTNode current=new BTNode(); current.L=L; current.R=R;
        if(L==R) { //只有一个节点
            current.max=A[L];   current.sum=A[L];
        }
        else{ int mid=(L+R)/2;       //中点mid
            BTNode leftchild=Build(L,mid);    //递归去建立左子树
            BTNode rightchild=Build(mid+1,R);   //递归去建立右子树
            current.left=leftchild; current.right=rightchild;  //把左右子树链接起来
            current.sum=leftchild.sum+rightchild.sum;    //计算统计量
            current.max=(leftchild.max>rightchild.max) ? leftchild.max:rightchild.max;
        }
        return current;
    }

    int QueryMax(BTNode node,int L, int R){
        if(node.L==L && node.R==R) return  node.max;  //刚好就是node的区间
        int nodemid=(node.L+node.R)/2;
        if(R<=nodemid) return QueryMax(node.left,L,R);
        if(L>nodemid)  return QueryMax(node.right,L,R);
        int leftmax=QueryMax(node.left,L,nodemid);
        int rightmax=QueryMax(node.right,nodemid+1, R);
        return (leftmax>rightmax) ? leftmax:rightmax;
    }

    int QuerySum(BTNode node,int L, int R){
        if(node.L==L && node.R==R) return  node.sum;  //刚好就是node的区间
        int nodemid=(node.L+node.R)/2;    //取出中点
        if(R<=nodemid) return QuerySum(node.left,L,R);//完全在左子树
        if(L>nodemid) return QuerySum(node.right,L,R);
        return QuerySum(node.left,L,nodemid)+QuerySum(node.right,nodemid+1,R);
        
    }
    
    void Update(BTNode node,int index,int newvalue) {
    	if(node.L==index&&node.R==index) {
    		node.sum=newvalue;  node.max=newvalue;
    		return;
    	}
    	int mid=(node.L+node.R)/2;
    	if(index<=mid) Update(node.left,index,newvalue);
    	else Update(node.right,index,newvalue);
    	node.sum=node.left.sum+node.right.sum;
    	node.max=(node.left.max>node.right.max)?node.left.max:node.right.max;
    }
       
       
        

	class BTNode{
		int L,R;
		int max,sum;
		BTNode left,right;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
Main tk=new Main();
	}

}