有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操作的結果。

對于20%的數據n <= 100，m <= 200。

對于50%的數據n <= 5000，m <= 5000。

對于100%的數據1 <= n <= 100000，m <= 100000，0 <= 格子權值 <= 10000。

思路:線段樹模板！就是最大值這個地方我有點搞混了；；；

#include<bits/stdc++.h>#define N 100010using namespace std;int t[4*N],tt[4*N],a[N];int s,maxn;void build(int l,int r,int d){	if(l==r)	{		t[d]=a[l];		tt[d]=a[l];		return ;	}	int mid=(l+r)/2;	build(l,mid,2*d);	build(mid+1,r,2*d+1);	t[d]=t[2*d]+t[2*d+1];	tt[d]=max(tt[2*d],tt[2*d+1]);	return ;}void update(int pos,int l,int r,int d,int num)//單點更新{	if(l==r)	{		t[d]=num;		tt[d]=num;		return ;	}	int mid=(l+r)/2;	if(pos<=mid)		update(pos,l,mid,2*d,num);	else		update(pos,mid+1,r,2*d+1,num);	t[d]=t[2*d]+t[2*d+1];	tt[d]=max(tt[2*d],tt[2*d+1]);	return ;}int query(int l,int r,int L,int R,int d)//和查詢{	if(l==L&&r==R)	{	 	return t[d];	}	int mid=(L+R)/2;	if(r<=mid)	{		return query(l,r,L,mid,2*d);	}	else if(l>mid)	{		return query(l,r,mid+1,R,2*d+1);	}	else	return  query(l,mid,L,mid,2*d)+query(mid+1,r,mid+1,R,2*d+1);//左右都需要查詢的時候傳入的 參數都是mid 和mid+1}int queryma(int l,int r,int L,int R,int d)//查詢最大值{	if(l<=L&&R<=r)		return tt[d];	int mid=(L+R)/2;	int ret=0;	if(l<=mid)//有區間在左面,就查詢左區間的最大值	ret=max(ret,queryma(l,r,L,mid,2*d));	if(r>mid)	ret=max(ret,queryma(l,r,mid+1,R,2*d+1));//有區間在右面就查詢右區間的最大值	return ret;	}int main(){	int p,x,y,n,m,s;	scanf("%d %d",&n,&m);	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);	build(1,n,1);	for(int i=0;i<m;i++)	{		scanf("%d %d %d",&p,&x,&y);		if(p==1)		{			update(x,1,n,1,y);		}		else  if(p==2)		{			 s=query(x,y,1,n,1);			 PRintf("%d/n",s);		}		else		{	maxn=queryma(x,y,1,n,1);			 printf("%d/n",maxn);		}	}}