线段树之成段更新（区间最大连续和）

题目描述：

给定一个含有N个整数的序列，它们的下标从1到N，对该序列进行如下2种操作；
0 a b将下标为a的值变为b。
1 a b求下标[a,b]之间的最大连续和

解题思路：

每一段区间当中必须记录相应的值以便于更新，其中的值包括了该区间的最大左连续和、最大右连续和、最大连续和以及总和，如图分析：

那么线段树此时从下往上更新的时候，合并区间时，那么对于此时我们要维护的区间最大连续和最多有三个值能够取，左区间最大连续和、右区间最大连续和、左区间的右最大连续和 + 右区间的左最大连续和，那么此时维护起来就特别的简单了。。

代码如下：

View Code

 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 const int N = 50003;
 5 struct node
 6 {
 7        int mmax,lmax,rmax,sum;       
 8 }tree[N<<2];
 9 void pushup(int t)
10 {
11      int t1=t<<1;
12      int t2=t1|1; 
13      tree[t].sum=tree[t1].sum+tree[t2].sum;
14      tree[t].mmax=max(tree[t1].mmax,tree[t2].mmax);
15      tree[t].mmax=max(tree[t].mmax,tree[t1].rmax+tree[t2].lmax);
16      tree[t].lmax=max(tree[t1].lmax,tree[t1].sum+tree[t2].lmax);
17      tree[t].rmax=max(tree[t2].rmax,tree[t2].sum+tree[t1].rmax);
18 }
19 void build(int t,int l,int r)
20 {
21      if(l==r)
22      {
23         scanf("%d",&tree[t].sum);
24         tree[t].mmax=tree[t].lmax=tree[t].rmax=tree[t].sum;
25         return ;
26      }
27      int m=(l+r)>>1;
28      build(t<<1,l,m);
29      build(t<<1|1,m+1,r);
30      pushup(t);
31 }
32 void update(int t,int l,int r,int i,int val)
33 {
34      if(l==r)
35      {
36          tree[t].lmax=tree[t].rmax=tree[t].mmax=tree[t].sum=val;
37          return ;
38      }
39      int m=(l+r)>>1;
40      if(i<=m)update(t<<1,l,m,i,val);
41      else update(t<<1|1,m+1,r,i,val);
42      pushup(t);
43 }
44 node query(int t,int l,int r,int L,int R)
45 {
46      if(L<=l&&r<=R)
47      return tree[t];
48      int m=(l+r)>>1;
49      node ans1,ans2,ans;
50      int flag1=0,flag2=0;
51      if(L<=m){ans1=query(t<<1,l,m,L,R);flag1=1;}
52      if(R>m){ans2=query(t<<1|1,m+1,r,L,R);flag2=1;}
53      if(flag1&&flag2)
54      {
55         ans.sum=ans1.sum+ans2.sum;
56         ans.lmax=max(ans1.lmax,ans1.sum+ans2.lmax);
57         ans.rmax=max(ans2.rmax,ans2.sum+ans1.rmax);
58         ans.mmax=max(max(ans1.mmax,ans2.mmax),ans1.rmax+ans2.lmax);
59      }
60      else
61      {
62         if(flag1) ans=ans1;
63         else   ans=ans2;
64      }
65      return ans;
66 }
67 int main()
68 {
69     int n,m,order,a,b;
70     while(~scanf("%d%d",&n,&m))
71     {
72           build(1,1,n);
73           for(int i=0;i<m;i++)
74           {
75               scanf("%d%d%d",&order,&a,&b);
76               if(order)
77               {
78                  if (a>b)swap(a,b); 
79                  node ans=query(1,1,n,a,b);
80                  printf("%d\n",ans.mmax);
81               }
82               else
83               update(1,1,n,a,b);        
84           }
85     }
86     return 0;    
87 }