segTree tree

rangeModule.cc

class STNode{
public:
    long l, r, m;
    bool tracked;
    STNode * lnode, * rnode;
    STNode(int ll, int rr):l(ll), r(rr), lnode(nullptr), rnode(nullptr){
        m = (l+r)/2;
        tracked = false;
    }
    
    void remove(STNode * node){
        if(!node) {node = nullptr; return;}
        remove(node->lnode);
        //node->lnode = nullptr;
        remove(node->rnode);
        //node->rnode = nullptr;
        delete node;
        //node = nullptr;
    }
    
    void addTrack(int left, int right){
        if(left >= r || right <= l) return;
        if(left <= l && right >= r) {
            remove(lnode); lnode = nullptr;
            remove(rnode); rnode = nullptr;
            tracked = true;
            return;
        }
        //cout<<left<<" "<<right<<" l "<<l<<" r "<<r<<endl;
        //int m = (l+r)>>1;
        godown();
        if(left <= m) lnode->addTrack(left, right);
        if(right>= m) rnode->addTrack(left, right);
        maintain();
    }
    
    void maintain(){
        tracked = lnode->tracked && rnode->tracked;
    }
    
    void godown(){
        if(!lnode || !rnode) {
            lnode = new STNode(l, m);
            lnode->tracked = tracked;
            rnode = new STNode(m, r);
            rnode->tracked = tracked;
        }
    }
    
    bool query(int left, int right){
        //if(tracked == false) return false;
        //cout<<left<<" "<<right<<" (l "<<l<<" r "<<r<<") tracked = "<<tracked<<endl;
        if(left <= l && r <= right) {
            return tracked;
        }
        if(left >= r || right <= l) return true; // out of range
        //if(!tracked) return false;                
        if(!lnode && !rnode) return tracked;
        bool res = true;
        if(left <= m && lnode) res = res && lnode->query(left, right);
        if(right>= m && rnode) res = res && rnode->query(left, right);
        return res;        
    }
    
    void removeTrack(int left, int right){
        if(left >= r || right <= l) return;
        if(left <= l && r <= right) {
            remove(lnode); lnode = nullptr;
            remove(rnode); rnode = nullptr;
            tracked = false; 
            return;
        }
        //cout<<left<<" "<<right<<" l "<<l<<" r "<<r<<endl;
        godown();
        if(left <= m) lnode->removeTrack(left, right); 
        if(right >= m) rnode->removeTrack(left, right);        
        maintain();
    }
        
};

class RangeModule {
public: 
    STNode * root;
    RangeModule() {
        root = new STNode(1, 1000000000);        // share_ptr
    }
    
    void addRange(int left, int right) {
        root->addTrack(left, right);
    }
    
    bool queryRange(int left, int right) {
        return root->query(left, right);
    }
    
    void removeRange(int left, int right) {
        root->removeTrack(left, right);
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * bool param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */