ZCMU--1852: 操作格子(线段树板子题)
Description
有n个格子，从左到右放成一排，编号为1-n。 共有m次操作，有3种操作类型：
1.修改一个格子的权值
2.求连续一段格子权值和
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
Input
第一行2个整数n，m。 接下来一行n个整数表示n个格子的初始权值。 接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
数据规模与约定 对于20%的数据n < = 100，m < = 200。 对于50%的数据n < = 5000，m < = 5000。 对于100%的数据1 < = n < = 100000，m < = 100000，0 < = 格子权值 < = 10000。
Output
有若干行，行数等于p=2或3的操作总数。 每行1个整数，对应了每个p=2或3操作的结果。
Sample Input
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4 Sample Output
6
3解析：线段树最基础单点修改，维护区间最值，区间和。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+5;
struct s
{int l,r,sum,x;//分别存区间和与区间最值
}tr[N*4];
int a[N];
void pushup(int u)
{tr[u].x=max(tr[u*2].x,tr[u*2+1].x);tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void build(int u,int l,int r)
{if(l==r) tr[u]={l,l,a[l],a[l]};else{tr[u]={l,r};int mid=l+r>>1;build(u*2,l,mid);build(u*2+1,mid+1,r);pushup(u);}
}
void modify(int u,int p,int v)//单点修改
{if(tr[u].l==tr[u].r&&tr[u].l==p) tr[u].x=tr[u].sum=v;else{int mid=tr[u].l+tr[u].r>>1;if(p<=mid) modify(u*2,p,v);else modify(u*2+1,p,v);pushup(u);}
}
int query1(int u,int l,int r)//返回区间和
{if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;int mid=tr[u].l+tr[u].r>>1;int ans=0;if(r<=mid) ans+=query1(u*2,l,r);else if(l>mid) ans+=query1(u*2+1,l,r);else ans+=query1(u*2,l,r)+query1(u*2+1,l,r);return ans;
}
int query2(int u,int l,int r)//返回区间最大值
{if(l<=tr[u].l&&r>=tr[u].r) return tr[u].x;int mid=tr[u].l+tr[u].r>>1;int ans=0;if(r<=mid) ans=max(ans,query2(u*2,l,r));else if(l>mid) ans=max(ans,query2(u*2+1,l,r));else ans=max(query2(u*2,l,r),query2(u*2+1,l,r));return ans;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==1) modify(1,x,y);else if(op==2) printf("%d\\n",query1(1,x,y));else printf("%d\\n",query2(1,x,y));} return 0;
}