Lucifer1729's blog

By Lucifer1729, history, 19 months ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
19 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

After making these two corrections, your code gets accepted.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You mean without Segment Tree?

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah or some easier implementation with segment tree

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

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

          Spoiler
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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):

          Spoiler
»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think you can find it yourself now)

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