# 【CSES】1190. Subarray Sum Queries

## [題目連結](https://cses.fi/problemset/task/1190)

## **時間複雜度**

* $O(MlogN)$

## **解題想法**

這題其實沒有很難實作，難的部分是想到線段樹怎麼往上轉移

這題最關鍵的點在你要先知道線段樹要存四個資料，分別為：

1. 區間 $[L, R]$ 的最大子陣列和 — $sum$
2. 區間 $[L, R]$ 的最大前綴，且一定要包含 $a_{L}$ — $prefix$
3. 區間 $[L, R]$ 的最大後綴，且依定要包含 $a_{R}$ — $suffix$
4. 區間 $[L, R]$ 的答案 — $ans$

當我們要將兩個節點 $nL$ 和 $nR$ 往父親節點 $fa$ 轉移時，我們可以按照以下的轉移式進行轉移：

1. $fa.sum$ $=$ $nL.sum$ + $nR.sum$
2. $fa.prefix$ $=$ max ( $nL.prefix$, $nL.sum$ + $nR.prefix$ )
3. $fa.suffix$ $=$ max ( $nR.suffix$, $nR.sum$ + $nL.suffix$ )
4. $fa.ans$ $=$ max ( $nL.ans$, $nR.ans$, $nL.suffix$ + $nR.prefix$ )

透過這樣就能夠建構出一顆足以完成題目需求的線段樹了

## **完整程式**

實作這邊值得注意的是，在最一開始 Build 跟 Update 要更新某個節點的資料的時候，記得 $ans$、$prefix$、$suffix$ 都要跟 0 取一次 max（因為題目有說可以包含空集合）

/* Question : CSES 1190. Subarray Sum Queries */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

#define nL cnt * 2
#define nR cnt * 2 + 1

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, m, a, b, arr[MAXN];

struct Node{
    int prefix, suffix, sum, ans;
} seg[MAXN * 4];

void update( int L, int R, int pos, int val, int cnt ){
    if( R < L || pos > R || pos < L ) return;
    if( pos == L && pos == R ){
        seg[cnt].sum = max((long long)0, val);
        seg[cnt].prefix = max((long long)0, val);
        seg[cnt].suffix = max((long long)0, val);
        seg[cnt].sum = val;
        return;
    }

    int M = (L + R) / 2;
    update(L, M, pos, val, nL);
    update(M+1, R, pos, val, nR);

    seg[cnt].sum = seg[nL].sum + seg[nR].sum;
    seg[cnt].prefix = max( seg[nL].prefix, seg[nL].sum + seg[nR].prefix );
    seg[cnt].suffix = max( seg[nR].suffix, seg[nR].sum + seg[nL].suffix );
    seg[cnt].ans = max( max( seg[nL].ans, seg[nR].ans ), seg[nL].suffix + seg[nR].prefix );
}

void build( int L, int R, int cnt ){
    if( L == R ){
        seg[cnt].sum = max((long long)0, arr[L]);
        seg[cnt].prefix = max((long long)0, arr[L]);
        seg[cnt].suffix = max((long long)0, arr[L]);
        seg[cnt].sum = arr[L];
        return;
    }

    int M = ( L + R ) / 2;
    build(L, M, nL);
    build(M+1, R, nR);

    seg[cnt].sum = seg[nL].sum + seg[nR].sum;
    seg[cnt].prefix = max( seg[nL].prefix, seg[nL].sum + seg[nR].prefix );
    seg[cnt].suffix = max( seg[nR].suffix, seg[nR].sum + seg[nL].suffix );
    seg[cnt].ans = max( max( seg[nL].ans, seg[nR].ans ), seg[nL].suffix + seg[nR].prefix );
}

signed main(){
    opt;
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i++ ) cin >> arr[i];
    build(1, n, 1);

    while( m-- ){
        cin >> a >> b;
        update(1, n, a, b, 1);
        cout << seg[1].ans << "\n";
    }
}