TREAP RANGE QUERY (but it's runtime is not that good), C++ (gcc)

TREAP RANGE QUERY (but it's runtime is not that good)

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

// SLOWER :(

struct Treap{
    struct node{
        ll sum, lazy, val;
        ll prior;
        ll cnt;
        node *l, *r;
        
        node(ll p, ll sum = 0, node* lft = NULL, node* rgt = NULL){}
    };
    
    typedef node* pnode;
    
    int get_cnt(pnode p){
        return p? p -> cnt : 0;
    }
    
    void upd_(pnode r){
        if(r){
            r -> cnt = get_cnt(r -> l) + get_cnt(r -> r) + 1;
            r -> sum = ((r -> l)? r -> l -> sum : 0) + ((r -> r)? r -> r -> sum : 0) + r -> val;
        }
    }
    
    void push(pnode root){
        if(!root) return;
        
        if(root -> l){
            pnode l = root -> l;
            l -> val += root -> lazy;
            l -> sum += l -> cnt * root -> lazy;
            l -> lazy += root -> lazy;
        }
        if(root -> r){
            pnode r = root -> r;
            r -> val += root -> lazy;
            r -> sum += r -> cnt * root -> lazy;
            r -> lazy += root -> lazy;
        }
        root -> lazy = 0;
    }
    
    void split(pnode root, pnode& l, pnode& r, int ind){
        if(!root) return void(l = r = NULL);
        push(root);
        
        int cur = get_cnt(root -> l) + 1;
        if(ind < cur) split(root -> l, l, root -> l, ind), r = root;
        else split(root -> r, root -> r, r, ind-cur), l = root;
        
        upd_(root);
    }
    
    void merge(pnode &root, pnode l, pnode r){
        push(l), push(r);
        if(!l || !r) return void(root = l? l : r);
        
        if(l -> prior > r -> prior) merge(l -> r, l -> r, r), root = l;
        else merge(r -> l, l, r -> l), root = r;
        
        upd_(root);
    }
    
    void update(int l, int r, ll val){
        pnode t1, t2, t3;
        split(root, t1, t2, l-1);
        split(t2, t2, t3, r - (l-1));
        
        /*cout << t2 -> sum << " " << val << " " << t2 -> cnt << endl;
        print(t2);
        cout << endl;*/
        
        t2 -> sum += t2 -> cnt*val;
        t2 -> lazy += val;
        t2 -> val += val;
        
        merge(t2, t2, t3);
        merge(root, t1, t2);
    }
    
    void insert(int pos, ll val){
        ll p = rand();
        pnode cur = new node(p, val);
        cur -> cnt = 1;
        
        pnode l, r;
        split(root, l, r, pos-1);
        merge(l, l, cur);
        merge(root,  l, r);
    }
    
    ll query(int l, int r){
        pnode t1, t2, t3;
        split(root, t1, t2, l-1);
        split(t2, t2, t3, r-(l-1));
        
        ll ans = t2 -> sum;
        
        merge(t2, t2, t3);
        merge(root, t1, t2);
        return ans;
    }
    
    void print(pnode root){
        if(!root) return;
        print(root -> l);
        cout << "(" << root -> val << " " << root -> lazy << ")  ";
        print(root -> r);
    }
    
    void print(){
        print(root);
        cout << endl;
    }
        
    Treap() : root (NULL){}
    private : 
        pnode root;
};

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    scanf("%d",&t);
    while(t--){
        int n, c;
        scanf("%d %d",&n ,&c);
        
        Treap tp;
        for(int j = 1; j <= n; j++)
            tp.insert(j, 0);
        
        //tp.print();
        while(c--){
            int typ, p, q;
            scanf("%d %d %d",&typ, &p ,&q);
            if(typ == 0){
                int val;
                scanf("%d",&val);
                tp.update(p, q, val);
                //tp.print();
            }
            else printf("%lld\n",tp.query(p, q));
        }
    }
    return 0;
}


run \| edit \| history \| help	0