Block Tree

#include <bits/stdc++.h>
#define MAX 10007

using namespace std;
typedef pair<int, int> pii;

struct node{
    int val, lazy;
    node *p,  *s, *t, *q;

    node(){}
    node(int _val, int _lazy){
        val = _val;
        lazy = _lazy;
        p = NULL;
        s = NULL;
        t = NULL;
        q = NULL;
    }
};

node *bt;

bool check(pii x, pii y, pii w) {
    if (w.first > x.first && w.first < x.second
    && w.second > x.second && w.second < y.second) return true;
    return false;
}

void add(node * no, pii l, pii r, int val){
    no->lazy += val;
    no->val += val*(r.second-r.first)*(l.second-l.first);
}

void dolazy(node *no, pii l, pii r){
    int mid1 = (l.first + r.first)/2;
    int mid2 = (l.second + r.second)/2;

    if(no->t == NULL) no->t = new node(0, 0);
    add(no->t, l, make_pair(mid1, mid2), no->lazy);
    if(no->p == NULL) no->p = new node(0, 0);
    add(no->p, make_pair(mid1+1, mid2+1), r, no->lazy);
    if(no->q == NULL) no->q = new node(0, 0);
    add(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), no->lazy);
    if(no->s == NULL) no->s = new node(0, 0);
    add(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), no->lazy);
    no->lazy = 0;
}

void update(node * no, pii l, pii r, pii x, pii y, int val){
    if(!check(x, y, l) && !check(x, y, r)) return;
    else if(check(x, y, l) && check(x, y, r)){
        no->lazy = val;
        no->val = val*(r.second-r.first)*(l.second-l.first);
    }else{
        int mid1 = (l.first + r.first)/2;
        int mid2 = (l.second + r.second)/2;
        dolazy(no, x, y);

        update(no->t, l, make_pair(mid1, mid2), x, y, val);
        update(no->p, make_pair(mid1+1, mid2+1), r, x, y, val);
        update(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), x, y, val);
        update(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), x, y, val);

        no->val = no->p->val + no->s->val + no->t->val + no->q->val;
    }
}

int query(node * no, pii l, pii r, pii x, pii y){
    if(!check(x, y, l) && !check(x, y, r)) return 0;
    else if(check(x, y, l) && check(x, y, r)) return no->val;
    else{
        int mid1 = (l.first + r.first)/2;
        int mid2 = (l.second + r.second)/2;
        dolazy(no, x, y);

        return query(no->t, l, make_pair(mid1, mid2), x, y) +
               query(no->p, make_pair(mid1+1, mid2+1), r, x, y) +
               query(no->q, make_pair(mid1+1, l.second), make_pair(r.first, mid2), x, y) +
               query(no->s, make_pair(l.first, mid2+1), make_pair(mid1, r.second), x, y);
    }
}
int main(){
    bt = new node(0,0);
    return 0;
}