data-structure/link-cut-tree/reversible-bbst.hpp

• View this file on GitHub
• Last update: 2024-06-10 16:05:09+07:00
• Include: #include "data-structure/link-cut-tree/reversible-bbst.hpp"

Required by

• data-structure/link-cut-tree/link-cut-tree.hpp
• data-structure/link-cut-tree/reversible-splay-tree.hpp

Verified with

• verify/yosupo/data-structure/range_reverse_range_sum.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-04-13
 * Description: Revesible BBST Base.
 */

template<class Tree,class Node,class Monoid>
struct ReversibleBBST:Tree{
    using Tree::merge;
    using Tree::split;
    using typename Tree::Ptr;
    using T = typename Monoid::value_type;

    ReversibleBBST()=default;

    T sum(Ptr t){
        return t?t->sum:T();
    }
    void pull(Ptr t){
        if(!t)return;
        t->size=1;
        t->sum=t->val;
        t->revsum=t->val;
        if(t->l){
            t->size+=t->l->size;
            t->sum=Monoid::op(t->l->sum,t->sum);
            t->revsum=Monoid::op(t->revsum,t->l->revsum);
        }
        if(t->r){
            t->size+=t->r->size;
            t->sum=Monoid::op(t->sum,t->r->sum);
            t->revsum=Monoid::op(t->r->revsum,t->revsum);
        }
    }
    void push(Ptr t){
        if(!t)return;
        if(t->rev){
            toggle(t->l);
            toggle(t->r);
            t->rev=false;
        }
    }
    void toggle(Ptr t){
        if(!t)return;
        swap(t->l,t->r);
        swap(t->sum,t->revsum);
        t->rev^=true;
    }
    T query(Ptr &t,int l,int r){
        if(l>r)return T();
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        T res=sum(y.first);
        t=merge(x.first,merge(y.first,y.second));
        return res;
    }
    void reverse(Ptr &t,int l,int r){
        if(l>r)return;
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        toggle(y.first);
        t=merge(x.first,merge(y.first,y.second));
    }
};

#line 2 "data-structure/link-cut-tree/reversible-bbst.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-13
 * Description: Revesible BBST Base.
 */

template<class Tree,class Node,class Monoid>
struct ReversibleBBST:Tree{
    using Tree::merge;
    using Tree::split;
    using typename Tree::Ptr;
    using T = typename Monoid::value_type;

    ReversibleBBST()=default;

    T sum(Ptr t){
        return t?t->sum:T();
    }
    void pull(Ptr t){
        if(!t)return;
        t->size=1;
        t->sum=t->val;
        t->revsum=t->val;
        if(t->l){
            t->size+=t->l->size;
            t->sum=Monoid::op(t->l->sum,t->sum);
            t->revsum=Monoid::op(t->revsum,t->l->revsum);
        }
        if(t->r){
            t->size+=t->r->size;
            t->sum=Monoid::op(t->sum,t->r->sum);
            t->revsum=Monoid::op(t->r->revsum,t->revsum);
        }
    }
    void push(Ptr t){
        if(!t)return;
        if(t->rev){
            toggle(t->l);
            toggle(t->r);
            t->rev=false;
        }
    }
    void toggle(Ptr t){
        if(!t)return;
        swap(t->l,t->r);
        swap(t->sum,t->revsum);
        t->rev^=true;
    }
    T query(Ptr &t,int l,int r){
        if(l>r)return T();
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        T res=sum(y.first);
        t=merge(x.first,merge(y.first,y.second));
        return res;
    }
    void reverse(Ptr &t,int l,int r){
        if(l>r)return;
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        toggle(y.first);
        t=merge(x.first,merge(y.first,y.second));
    }
};

Back to top page