考察:线段树
思路:
参考线段树模板.对于线段树结点我们需要定义使得能求出连续区间的子段和.
- [l,r]这是模板
- maxn 表示[l,r]区间内最大的连续子段和.
但是这样我们能从子节点的子段和推到父节点吗?答案是不能的.考虑父节点的子段和要如何求.父节点的maxn有三个来源:
(1) 左子节点的子段和
(2) 右子节点的子段和
(3) 左子节点的最大后缀和+右子节点的最大前缀和.
由此还需要记录最大后缀和和最大前缀和.但是最大后缀和与最大前缀和怎么算呢?
也分两种情况. if(最大前缀和长度>mid-l+1) 那么 最大前缀和 = 左子节点和+右子节点的最大前缀和
else 最大前缀和 = 左子节点的最大前缀和.
同理最大后缀和.
还需要注意的一个问题是query函数.我们求的是给定[L,R]区间内的最大子段和.也就是我们需要构造一个结点区间在[L,R]区间内.
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 const int N = 500010,INF = 1e9;
5 int n,m,a[N];
6 struct Node{
7 int l,r,maxn,L,R,sum;//左区间,右区间,最大值,后缀和,前缀和,总和
8 Node operator=(const Node& n){
9 this->l = n.l,this->r = n.r;
10 this->L = n.L,this->R = n.R;
11 this->maxn = n.maxn;
12 return *this;
13 }//这里的maxn是当前[l,r]区间的最大值
14 }tr[N<<2];
15 void push_up(int u)
16 {
17 tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
18 tr[u].L = max(tr[u<<1].L,tr[u<<1].sum+tr[u<<1|1].L);
19 tr[u].R = max(tr[u<<1|1].R,tr[u<<1|1].sum+tr[u<<1].R);
20 tr[u].maxn = max(tr[u<<1].maxn,tr[u<<1|1].maxn);
21 tr[u].maxn = max(tr[u<<1].R+tr[u<<1|1].L,tr[u].maxn);
22 }
23 void pushup(Node& u,Node& L,Node& R)
24 {
25 u.sum = L.sum+R.sum;
26 u.L = max(L.L,L.sum+R.L);
27 u.R = max(R.R,R.sum+L.R);
28 u.maxn = max(L.maxn,R.maxn);
29 u.maxn = max(L.R+R.L,u.maxn);
30 }
31 void build(int u,int l,int r)
32 {
33 tr[u].l = l,tr[u].r = r;
34 if(l==r)
35 {
36 tr[u].maxn = a[l];
37 tr[u].L = a[l],tr[u].R = a[r];
38 tr[u].sum = a[l];
39 return;
40 }
41 int mid = l+r>>1;
42 build(u<<1,l,mid); build(u<<1|1,mid+1,r);
43 push_up(u);
44 }
45 void modify(int u,int idx,int x)
46 {
47 if(tr[u].l==tr[u].r)
48 {
49 tr[u].L = tr[u].R = tr[u].maxn = x;
50 tr[u].sum = x;
51 return;
52 }
53 int mid = tr[u].l+tr[u].r>>1;
54 if(idx<=mid) modify(u<<1,idx,x);
55 else modify(u<<1|1,idx,x);
56 push_up(u);
57 }
58 Node query(int u,int l,int r)
59 {
60 if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
61 int mid = tr[u].l+tr[u].r>>1;
62 if(r<=mid) return query(u<<1,l,r);
63 else if(l>mid) return query(u<<1|1,l,r);
64 else{
65 Node L = query(u<<1,l,r);
66 Node R = query(u<<1|1,l,r);
67 Node res;
68 pushup(res,L,R);
69 return res;
70 }
71 }
72 int main()
73 {
74 scanf("%d%d",&n,&m);
75 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
76 build(1,1,n);
77 while(m--)
78 {
79 int k,x,y;
80 scanf("%d%d%d",&k,&x,&y);
81 if(k==1)
82 {
83 if(x>y) swap(x,y);
84 printf("%d\n",query(1,x,y).maxn);
85 }else modify(1,x,y);
86 }
87 return 0;
88 }
89