Segment With Maximum Sum

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	awoo	158
4	cry	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	maroonrk	152

I tried to code solution for the Segment With Maximum Sum problem from the Segment Trees Section in ITMO pilot course. Link To the Question

class Sgtree{
private:
    vl seg,pref,suff,sum;
    int _n;
 
    void leaf_update(ll node,ll val) {
        pref[node] = val;
        suff[node] = val;
        seg[node] = val;
        sum[node] = val;
    }
 
    void nonLeaf_update(ll node) {
        sum[node] = sum[2*node] + sum[2*node+1];
        pref[node] = max(pref[2*node],sum[2*node]+pref[2*node+1]);
        suff[node] = max(pref[2*node+1],sum[2*node+1]+suff[2*node]);
        seg[node] = max({seg[2*node],seg[2*node+1],suff[2*node]+pref[2*node+1]});
    }
public:
    Sgtree(vl& arr){
        _n = arr.size();
        // increasing size of array untill it becomes power of 2
        while((_n&(_n-1)) != 0) {
            arr.pb(0ll);
            _n++;
        }
 
        seg.resize(2*_n);
        pref.resize(2*_n);
        suff.resize(2*_n);
        sum.resize(2*_n);
 
        build(1,0,_n-1,arr);
    }
 
    void build(ll node,ll nl,ll nr,vl &arr){
        if(nl == nr){
            leaf_update(node,arr[nl]);
            return;
        }
        ll mid = (nl+nr) >> 1;
        build(2*node,nl,mid,arr);
        build(2*node+1,mid+1,nr,arr);
 
        nonLeaf_update(node);
    }
 
    // iterative version, O(logN)
    void point_update_itr(ll i,ll val) {
        leaf_update(_n+i,val);
 
        for(int j = (_n + i) / 2; j>=1; j /= 2)
            nonLeaf_update(j);
    }
 
    ll get_ans() {
        return max(seg[1],0ll);
    }
};

This is the code of my segment tree and i'm not able to find any mistake in this but this is giving WA on TC23.

Can anyone please tell me where am i doing wrong

Комментарии (8)

Показать архивные | Написать комментарий?

udta_kouwa

18 месяцев назад, # |

i think you should consider negative values in leaf_update as 0,0,0,val

→ Ответить

sreesh_56

← Rev. 3 →

Firstly, the other comment is correct — I don't think you're handling negative values correctly. You should be using max(0, val) in the first three lines of your leaf_update function. EDIT: never mind, I didn't see that you maximise your answer with 0.

Secondly, the third line of your nonLeaf_update is incorrect — see if you can spot the small bug.

Spoiler

It should be

    suff[node] = max(suff[2 * node + 1], sum[2 * node + 1] + suff[2 * node]);

instead.

After making these two corrections, your code gets accepted.

Lucifer1729

18 месяцев назад, # ^ |

By the way is there any better way to solve this ques?

SilverWing05

You mean without Segment Tree?

Yeah or some easier implementation with segment tree

← Rev. 2 →

Don't think there's a more easier implementation with Segment Tree. You can take a look at my submission.

struct Seg {
    long long amax = 0, pref = 0, suff = 0, sum = 0;
};
 
class SegTree {
private:
    vector<Seg> t;
public:
    SegTree(int n) : t(4 * n) {}
 
    Seg combine(Seg a, Seg b) {
        Seg t;
        t.amax = max({a.amax, b.amax, a.suff + b.pref});
        t.pref = max(a.pref, a.sum + b.pref);
        t.suff = max(b.suff, b.sum + a.suff);
        t.sum = a.sum + b.sum;
        return t;
    }
 
    void update(int i, int tl, int tr, int x, long long val) {
        if (tl > x || tr < x) return;
        if (tl == tr && tl == x) {
            t[i] = {max(val, 0LL), max(val, 0LL), max(val, 0LL), val}; return;
        }
 
        int m = (tl + tr) >> 1;
        update(2 * i, tl, m, x, val);
        update(2 * i + 1, m + 1, tr, x, val);
        t[i] = combine(t[2 * i], t[2 * i + 1]);
    }
 
    Seg maxSegment(int i, int tl, int tr, int l, int r) {
        if (tl > r || tr < l) return {0LL, 0LL, 0LL, 0LL};
        if (tl >= l && tr <= r) return t[i];
 
        int m = (tl + tr) >> 1;
        return combine(maxSegment(2 * i, tl, m, l, r), maxSegment(2 * i + 1, m + 1, tr, l, r));
    }
};
 
void solve() {
    int n, m;
    cin >> n >> m;
 
    SegTree ST(n);
    vector<long long> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        ST.update(1, 0, n - 1, i, v[i]);
    }
 
    cout << ST.maxSegment(1, 0, n - 1, 0, n - 1).amax << endl;
    for (int i = 0; i < m; i++) {
        int x, val;
        cin >> x >> val;
 
        ST.update(1, 0, n - 1, x, val);
        cout << ST.maxSegment(1, 0, n - 1, 0, n - 1).amax << endl;
    }
}

I don't think you can do it without a segment tree. I personally prefer iterative segment trees, so my implementation would look like this (but it's basically the same):

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

struct seg_tree {
    int n;
    vector<array<int64_t, 4>> t;

    seg_tree(int _n) : n(1 << (32-__builtin_clz(_n))), t(2 * n) {}

    void update(int i, int x) {
        t[i += n] = {max(x, 0), max(x, 0), max(x, 0), x};
        while (i /= 2) {
            auto [l_best, l_left, l_right, l_total] = t[2 * i]; 
            auto [r_best, r_left, r_right, r_total] = t[2 * i+1];
            t[i] = {max({l_best, r_best, l_right + r_left}), 
                    max(l_left, l_total + r_left), 
                    max(r_right, l_right + r_total), 
                    l_total + r_total};
        }
    }
};

int main() {
    int n, q;
    cin >> n >> q;

    seg_tree st(n);
    for (int i = 0, x; i < n; ++i) {
        cin >> x, st.update(i, x);
    }

    cout << st.t[1][0] << '\n';
    while (q--) { 
        int i, x;
        cin >> i >> x, st.update(i, x);
        cout << st.t[1][0] << '\n';
    }
}

I think you can find it yourself now)

suff[node] = max(pref[2*node+1],sum[2*node+1]+suff[2*node]);

Блог пользователя Lucifer1729