有n個(gè)格子，從左到右放成一排，編號(hào)為1-n。

共有m次操作，有3種操作類型：

1.修改一個(gè)格子的權(quán)值，

2.求連續(xù)一段格子權(quán)值和，

3.求連續(xù)一段格子的最大值。

對(duì)于每個(gè)2、3操作輸出你所求出的結(jié)果。

第一行2個(gè)整數(shù)n，m。

接下來(lái)一行n個(gè)整數(shù)表示n個(gè)格子的初始權(quán)值。

接下來(lái)m行，每行3個(gè)整數(shù)p,x,y，p表示操作類型，p=1時(shí)表示修改格子x的權(quán)值為y，p=2時(shí)表示求區(qū)間[x,y]內(nèi)格子權(quán)值和，p=3時(shí)表示求區(qū)間[x,y]內(nèi)格子最大的權(quán)值。

有若干行，行數(shù)等于p=2或3的操作總數(shù)。

每行1個(gè)整數(shù)，對(duì)應(yīng)了每個(gè)p=2或3操作的結(jié)果。

對(duì)于20%的數(shù)據(jù)n <= 100，m <= 200。

對(duì)于50%的數(shù)據(jù)n <= 5000，m <= 5000。

對(duì)于100%的數(shù)據(jù)1 <= n <= 100000，m <= 100000，0 <= 格子權(quán)值 <= 10000。

直接貼上代碼：

#include<iostream>#define MAX 100000using namespace std;struct seg_TreeNode{	int low, high;//區(qū)間左右端點(diǎn)	int value, max;//value在葉子節(jié)點(diǎn)表示權(quán)值，非葉子節(jié)點(diǎn)表示區(qū)間權(quán)值和，max表示區(qū)間內(nèi)最大值}tree[4*MAX];void initTree(int num,int low, int high){	if(low==high)	{		tree[num].low = tree[num].high = low;		cin >> tree[num].value;		tree[num].max =tree[num].value;		return;	}	tree[num].low = low;	tree[num].high = high;	int mid = (low + high) >> 1;	initTree(2 * num, low, mid);	initTree(2 * num+1, mid+1,high);	tree[num].max = tree[num * 2].max > tree[num * 2 + 1].max ? tree[num * 2].max : tree[num * 2 + 1].max;	tree[num].value = tree[num * 2].value + tree[num * 2 + 1].value;//此處線段樹建立采用后續(xù)遍歷，因?yàn)閰^(qū)間的權(quán)值和需要知道左區(qū)間和右區(qū)間的權(quán)值和。}void update(int num, int x, int y){	if (tree[num].low == tree[num].high)	{		tree[num].value = y;		tree[num].max = y;		return;	}	int mid = tree[num * 2].high;	if (mid >= x)		update(num * 2, x, y);	if (mid < x)        update(num * 2 + 1, x, y);	tree[num].value = tree[num * 2].value + tree[num * 2 + 1].value;	tree[num].max = tree[num*2].max < tree[num*2+1].max ? tree[num*2+1].max: tree[num*2].max;	return;}int query1(int num, int low, int high)//最大值{	if (tree[num].low == low&&tree[num].high == high)		return tree[num].max;	int mid = tree[num * 2].high;	if (mid >= high)		return query1(num * 2, low, high);	if (mid < low)		return query1(num * 2 + 1, low, high);	int le=query1(num * 2, low, mid);	int ri=query1(num * 2 + 1, mid + 1, high);	return le > ri?le:ri;}int query2(int num, int low, int high)//區(qū)間和{	if (tree[num].low == low&&tree[num].high == high)		return tree[num].value;	int mid = tree[num * 2].high;	if (mid >= high)		return query2(num * 2, low, high);	if (mid < low)		return query2(num * 2 + 1, low, high);	int le = query2(num * 2, low, mid);	int ri = query2(num * 2 + 1, mid + 1, high);	return le+ri;}int main(){	int a, b, c;	int m, n;	cin >> m >> n;	initTree(1, 1, m);	for (int i = 0;i < n;i++)	{		cin >> a >> b >> c;		switch (a)		{		case 1:update(1, b, c);break;		case 2:cout<<query2(1, b, c)<<endl;break;		case 3:cout<<query1(1, b, c)<<endl;break;		}	}	return 0;}