算法训练 操作格子 线段树

有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);		}	}}