SegTree_Doubt's blog

By SegTree_Doubt, 3 years ago, In English

Hi everyone! I was recently doing the EDU Segment Tree Part 2 (Thanks CodeForces for these wonderful tutorials!) and was solving the last problem (Assignment and Sum) and the Segment Tree struct looked something like this:

// Assignment and Sum

#define ll long long

struct SegTree {
    ll size;
    vector<ll> values;
    vector<ll> operations;

    ll NO_OPERATION = LLONG_MAX - 1;
    ll NEUTRAL_ELEMENT = 0;

    ll modify_op(ll a, ll b, ll len) {
        if(b == NO_OPERATION) return a;
        return len * b;
    }

    ll calc_op(ll a, ll b) {
        return a + b;
    }
    
    void apply_mod_op(ll& a, ll b, ll len) {
        a = modify_op(a,b,len);
    }

    void init(ll n){
        size = 1;
        while(size < n) size *= 2;
        values.assign(2*size,0LL);
        operations.assign(2*size,0LL);
    }

    void propagate(ll x, ll lx, ll rx){
        if(rx - lx == 1) return;
        ll m = (lx+rx)/2;
        apply_mod_op(operations[2*x+1],operations[x],1);
        apply_mod_op(values[2*x+1],operations[x],m - lx);
        apply_mod_op(operations[2*x+2],operations[x],1);
        apply_mod_op(values[2*x+2],operations[x],rx - m);
        operations[x] = NO_OPERATION;
    }

    void modify(ll l, ll r, ll v, ll x, ll lx, ll rx){
        propagate(x,lx,rx);
        if(lx >= r || l >= rx) return;
        if(lx >= l && rx <= r){
            apply_mod_op(operations[x],v,1);
            apply_mod_op(values[x],v,rx - lx);
            return;
        }
        ll mid = (lx+rx)/2;
        modify(l,r,v,2*x+1,lx,mid);
        modify(l,r,v,2*x+2,mid,rx);
        values[x] = calc_op(values[2*x+1],values[2*x+2]);
    }

    void modify(ll l, ll r, ll v){
        modify(l,r,v,0,0,size);
    }

    ll calc(ll l, ll r, ll x, ll lx, ll rx){
        propagate(x,lx,rx);
        if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if(lx >= l && rx <= r){
            return values[x];
        }
        ll mid = (lx+rx)/2;
        ll m1 = calc(l,r,2*x+1,lx,mid);
        ll m2 = calc(l,r,2*x+2,mid,rx);
        return calc_op(m1,m2);
    }

    ll calc(ll l, ll r){
        return calc(l,r,0,0,size);
    }
};

This Code currently works only for Assignment and Sum Operations but can be made work for Assignment and Min by changing NEUTRAL_ELEMENT = LLONG_MAX, modify_op and calc_op.

I wanted to make this Segment Tree a bit "generalized" so that it works for any operation. So, I tried to make this Segment Tree work for Addition and Sum, Addition and Minimum etc. For Addition and Sum, I tried changing the beginning lines to this:

    //Addition and Sum
    ll NEUTRAL_ELEMENT = 0;

    ll modify_op(ll a, ll b, ll len) {
        if(b == NO_OPERATION) return a * len;
        return len * b;
    }

    ll calc_op(ll a, ll b) {
        return a + b;
    }
    
    void apply_mod_op(ll& a, ll b, ll len) {
        a = modify_op(a,b,len);
    }
    //Addition and Minimum
    ll NEUTRAL_ELEMENT = LLONG_MAX;

    ll modify_op(ll a, ll b, ll len) {
        if(b == NO_OPERATION) return a;
        return len * b;
    }

    ll calc_op(ll a, ll b) {
        return min(a,b);
    }
    
    void apply_mod_op(ll& a, ll b, ll len) {
        a = modify_op(a,b,len);
    }

However, this does not work :( I've tried changing these values to whatever I could think of, Adding and Multiplying here and there, but I have no clue. So, I would be grateful if anybody could suggest me how to change these beginning few lines (everything else remains the same) in this Segment Tree struct to make it work for Addition and Minimum, Multiplication and Sum, Addition and Sum and Bitwise OR and AND.

Thanks!

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it