Try   HackMD

【CSES】1190. Subarray Sum Queries

題目連結

時間複雜度

  • O(MlogN)

解題想法

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

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

  1. 區間
    [L,R]
    的最大子陣列和 —
    sum
  2. 區間
    [L,R]
    的最大前綴,且一定要包含
    aL
    prefix
  3. 區間
    [L,R]
    的最大後綴,且依定要包含
    aR
    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"; } }