--- tags: 題解 --- # 最大連續和-線段樹/分治 ## 題序 給定一條長$N$的線段，並有$Q$次詢問 每次詢問有一個區間$[QL,QR]$，滿足$QL≤L≤R≤QR$中，求最大連續和 且若最大連續和小於$0$則輸出$0$ 輸入說明： 第一行有兩個正整數$N$和$Q$，分別代表縣段長度及詢問次數 第二行有$N$個正整數$A_i$，代表線段$1$~$N$ 接下來有$Q$行 每行有兩個正整數$QL$和$QR$，分別代表詢問的區間 $N≤100000$ $Q≤100000$ $-1000000000≤A_i≤1000000000$ $1≤QL≤QR≤N$ 輸出說明： 輸出指定區間內的最大連續和 每個答案輸出完換行 範例輸入： 4 3 1 -2 3 4 1 1 1 4 2 2 範例輸出： 1 7 0 ## 題解 //線段樹的細節觀念在這不祥細解釋，只講解和基本區間和線段數不同的分治觀念和pull //不熟線段樹的可以去看我線段樹的筆記[線段樹](/v9MArO34RFq-eWTRT5avWA) 我們在線段樹的每個節點中都存入-區間從左端開始的最大連續和、區間從右端開始的最大連續和、區間和、區間最大連續和 當我們從樹的底部開始向上更新時我們要分別更新這四個值 #define $lm$ 從左端開始的最大連續和 #define $rm$ 從右端開始的最大連續和 #define $ans$ 區間最大連續和 #define $sum$ 區間和 ### 從左端開始的最大連續和 父節點的$lm$只有兩種可能 1.左子節點的$lm$ 2.左子節點的$sum$ $+$ 右子節點的$lm$ 兩種取$max$就是父節點的$lm$ ### 從右端開始的最大連續和 父節點的$rm$一樣只有兩種可能 1.右子節點的$rm$ 2.右子節點的$sum$ + 左子節點的$rm$ 兩種取$max$就是父節點的$rm$ ### 區間最大連續和 父節點的區間最大連續和則有三種可能 1.左子節點的$ans$ 2.右子節點的$ans$ 3.左子節點的$rm$ + 右子節點的$lm$ 三種取$max$就是父節點的$ans$ ### 區間和 區間和就和一般的線段樹做法一樣 父節點的區間和等於左子節點$+$右子節點的和 ## 實作 ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long #define maxn 1000005 int n,t,a[maxn]; struct node{ int lm;//從左端開始的最大連續和 int rm;//從右端開始的最大連續和 int ans;//區間最大連續和 int sum;//區間和 }tree[maxn*4]; node pull(node lc,node rc){ node f; f.lm = max(lc.lm , lc.sum + rc.lm); f.rm = max(rc.rm , rc.sum + lc.rm); f.sum= lc.sum + rc.sum; f.ans= max(max(lc.ans , rc.ans) , lc.rm + rc.lm); return f; } void build(int l,int r,int rt){ if(l==r){ tree[rt].lm = tree[rt].rm = tree[rt].sum = tree[rt].ans = a[l]; return; } int mid=(l+r)>>1; build(l,mid,rt<<1) , build(mid+1,r,rt<<1|1); tree[rt] = pull(tree[rt<<1] ,tree[rt<<1|1]); } node query(int L,int R,int l,int r,int rt){ if(L <= l && R >= r ) return tree[rt]; int mid = (l+r) >> 1; if(R <= mid) return query(L,R,l,mid,rt<<1); else if(L > mid) return query(L,R,mid+1,r,rt<<1|1); else{ node back; back = pull (query(L,mid,l,mid,rt<<1),query(mid+1,R,mid+1,r,rt<<1|1)); return back; } } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> t; for(int i=1;i<=n;i++) cin >> a[i]; build(1,n,1); while(t--){ int x,y; cin >> x >> y; if(x>y) swap(x,y); int ans = query(x,y,1,n,1).ans; if(ans < 0) ans = 0; cout << ans << '\n'; } return 0; } ``` <!-- ```cpp= #include<bits/stdc++.h> using namespace std; #define int long long int n,t,a[1000005]; struct node{ int lm,rm,sum,ans; }tree[4000005]; void pull(int rt){ tree[rt].lm = max(tree[rt<<1].lm , tree[rt<<1].sum + tree[rt<<1|1].lm); tree[rt].rm = max(tree[rt<<1|1].rm , tree[rt<<1|1].sum + tree[rt<<1].rm); tree[rt].sum= tree[rt<<1].sum + tree[rt<<1|1].sum; tree[rt].ans= max(max(tree[rt<<1].ans , tree[rt<<1|1].ans) , tree[rt<<1].rm + tree[rt<<1|1].lm); } void build(int l,int r,int rt){ if(l==r){ tree[rt].lm = tree[rt].rm = tree[rt].sum = tree[rt].ans = a[l]; return; } int mid=(l+r)>>1; build(l,mid,rt<<1) , build(mid+1,r,rt<<1|1); pull(rt); } node query(int L,int R,int l,int r,int rt){ if(L <= l && R >= r ) return tree[rt]; int mid = (l+r) >> 1; if(R <= mid) return query(L,R,l,mid,rt<<1); else if(L > mid) return query(L,R,mid+1,r,rt<<1|1); else{ node back; node lct = query(L,mid,l,mid,rt<<1);//左子節點 node rct = query(mid+1,R,mid+1,r,rt<<1|1);//右子節點 back.lm = max(lct.lm,lct.sum+rct.lm); back.rm = max(rct.rm,rct.sum+lct.rm); back.ans = max(max(lct.ans,rct.ans),lct.rm+rct.lm); return back; } } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> t; for(int i=1;i<=n;i++) cin >> a[i]; build(1,n,1); while(t--){ int x,y; cin >> x >> y; if(x>y) swap(x,y); int ans = query(x,y,1,n,1).ans; if(ans < 0) ans = 0; cout << ans << '\n'; } return 0; } ``` --> 這題目有要求修改線段的話 更新的函數就和一般線段樹寫法差不多 ```cpp= void update(int pos,int val,int l,int r,int rt){ if(l == r){ tree[rt].lm = tree[rt].rm = tree[rt].sum = tree[rt].ans = val; return; } int mid=(l+r)>>1; if(pos<=mid) update(pos,val,l,mid,rt<<1); else update(pos,val,mid+1,r,rt<<1|1); tree[rt] = pull(tree[rt<<1],tree[rt<<1|1]); } ```