Segment Tree - Lazy

/*
            BISMILLAHIR-RAHMANIR-RAHIM
                    SWExSh4n.t0
                        SUST
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define debug 01

std::vector < ll > tree, lazy;
ll n;

void update ( ll node, ll node_low, ll node_high, ll query_low, ll query_high, ll val )
{
    if( lazy[node] > 0 ) {
        tree[node] = lazy[node] * (query_high - query_low + 1);
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }

    if( node_low >= query_low && node_high <= query_high ) {
        tree[node] += val * ( node_high - node_low + 1 );
        lazy[2*node] += val;
        lazy[2*node+1] += val;
        return;
    }
    if( node_low > query_high || node_high < query_low ) {
        return;
    }

    ll mid = ( node_high + node_low ) / 2;
    update( 2 * node, node_low, mid, query_low, query_high, val );
    update( 2 * node + 1, mid + 1, node_high, query_low, query_high, val );
    if( node_low != node_high ) tree[node] = tree[2*node] + tree[2*node+1];
    return;
}

ll getSum ( ll node, ll node_low, ll node_high, ll query_low, ll query_high )
{
    if( lazy[node] > 0 ) {
        tree[node] = lazy[node] * (query_high - query_low + 1);
        lazy[2*node] += lazy[node];
        lazy[2*node+1] += lazy[node];
        lazy[node] = 0;
    }

    if( node_low >= query_low && node_high <= query_high ) {
        return tree[node];
    }
    if( node_low > query_high || node_high < query_low ) {
        return 0;
    }
    ll mid = ( node_high + node_low ) / 2;

    ll sum = getSum( 2 * node, node_low, mid, query_low, query_high ) + getSum( 2 * node + 1, mid + 1, node_high, query_low, query_high );
    if( node_low != node_high ) {
        tree[node] = sum;
    }
    return tree[node];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t, q;
    t = 1;
    std::cin >> t;
    ll cs = 0;

    while( t-- ) {
        std::cin >> n >> q;
        while( __builtin_popcount(n) != 1 ) {
            n++;
        }
        tree.resize( 4 * n );
        lazy.resize( 4 * n );
        std::cout << "Case " << ++cs << ":\n";
        while( q-- ) {
            ll q_type;
            std::cin >> q_type;
            if( q_type == 0 ) {
                ll q_low, q_high, val;
                std::cin >> q_low >> q_high >> val;
                update( 1, 0, n-1, q_low, q_high, val );

            }
            else {
                ll q_low, q_high;
                std::cin >> q_low >> q_high;
                std::cout << getSum( 1, 0, n-1, q_low, q_high ) << endl;
            }
        }

        tree.clear();
        lazy.clear();
    }
    return 0;
}

//  ALHAMDULILLAH