问题描述 有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式 第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式 有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入 4 3 1 2 3 4 2 1 3 1 4 3 3 1 4 样例输出 6 3 数据规模与约定 对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。
这次多了一个特性，就是多求了一个区间段的最大值，不分析了。 代码：
import java.util.Scanner; class P//因为一个线段点不仅需要保存和值还要保存最大值，所以设了两个域值 { int sum; int max; P(int sum,int max) { this.sum=sum; this.max=max; } P(){} } public class Main { static P T[]; static Scanner sc; public static void main(String[] args) { sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); T=new P[n<<2]; buildUp(1,1,n);//建树 int x[]=new int[3]; while((m--)>0) { for(int i=0;i<3;i++) x[i]=sc.nextInt(); if(x[0]==1) change(x[1],x[2],1,1,n); else if(x[0]==2) System.out.println(querySum(x[1],x[2],1,1,n)); else System.out.println(queryMax(x[1],x[2],1,1,n)); } } static void buildUp(int s,int l,int r) { if(l==r) { int a=sc.nextInt(); T[s]=new P(a,a); return; } int m=(l+r)>>1; buildUp(s<<1,l,m); buildUp(s<<1|1,m+1,r); T[s]=new P(); T[s].sum=T[s<<1].sum+T[s<<1|1].sum; T[s].max=Math.max(T[s<<1].max, T[s<<1|1].max);//只是多了这行而已 } static void change(int p,int c,int s,int l,int r) { if(l==r&&l==p) { T[s].max=c; T[s].sum=c; return; } int m=(l+r)>>1; if(p<=m) change(p,c,s<<1,l,m); else change(p,c,s<<1|1,m+1,r); T[s].sum=T[s<<1].sum+T[s<<1|1].sum; T[s].max=Math.max(T[s<<1].max, T[s<<1|1].max);//同样的和值和最大值都要变 } static int querySum(int L,int R,int s,int l,int r) { if(L<=l&&r<=R)return T[s].sum; int m=(l+r)>>1; int ans=0; if(m>=L) ans+=querySum(L,R,s<<1,l,m); if(m<R) ans+=querySum(L,R,s<<1|1,m+1,r); return ans;//这里没变化 } static int queryMax(int L,int R,int s,int l,int r) { if(L<=l&&r<=R)return T[s].max; int m=(l+r)>>1; if(R<=m) return queryMax(L,R,s<<1,l,m);//进一步去缩小范围 if(m<L) return queryMax(L,R,s<<1|1,m+1,r); return Math.max(queryMax(L,R,s<<1,l,m), queryMax(L,R,s<<1|1,m+1,r));//如果m夹杂在R和L之间，那么我们就取他们的最大值，与求和函数还是有区别的 } }