---
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$
### 區間和
區間和就和一般的線段樹做法一樣
父節點的區間和等於左子節點$+$右子節點的和

## 實作

#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;
}

<!--

#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;
}

-->
這題目有要求修改線段的話
更新的函數就和一般線段樹寫法差不多

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]);
}