I am trying to solve this problem using sqrt_decomposition : http://www.spoj.com/problems/HORRIBLE/ Getting WA

Strategy used : 1. Two arrays, b for storing range sum, c for storing range change. 2. Whenever requested update, range which do not lie completely in a block is individually updated where as for a block range update only c. 3. same can be considered for query.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#define ll long long int
using namespace std;

int n, q, type, x, y, k;
ll a[10000000], b[1000000], c[1000000];
int bs, cnt;

void sqrt_decomposition() {

    bs = (int) sqrt(n + .0) + 1;
    
}

void update(int l, int r, int k) {

    int cl = l / bs, cr = r / bs;

    if(cl == cr) {

        for(int i = l; i <= r; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            c[i] += k;
        }

        for(int i = cr * bs; i <= r; ++i) {
            b[cr] += k - a[i];
            a[i] += k;
        }

    }
}

ll query(int l, int r) {

    int cl = l / bs, cr = r / bs;
    ll sum = 0;

    if(cl == cr) {

        for(int i = l; i <= r; ++i)
            sum += a[i] + c[cl];
    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            sum += a[i] + c[cl];
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            sum += b[i] + bs * c[i];
        }

        for(int i = cr * bs; i <= r; ++i) {
            sum += a[i] + c[cr];
        }

    }

    return sum;
}

int main() {

    ios_base::sync_with_stdio(false);

    int test;
    cin >> test;

    while(test--) {

        cin >> n >> q;

        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));

        sqrt_decomposition();

        while(q--) {

            cin >> type;

            if(type) {
                cin >> x >> y;
                cout << query(x - 1, y - 1) << endl;
            }

            else {
                cin >> x >> y >> k;
                update(x - 1, y - 1, k);
            }
        }

    }

    return 0;
}

Please Help.