Article:Sqrt Decomposition

Problem:
I think in math terms it's usually cleaner to think about intervals a[l,r) (begin index inclusive, end index exclusive) than a[l,r] (both inclusive). If you look at the structure of a for loop, we have termination condition i < n instead of i <= n-1. (Interestingly,Dijkstra covered why this is more natural as the length of the interval is just the difference between the bounds, so prevents messy "-1" factors floating around. )

So to make it easier to grasp what's going on without being obscured by indexing, the case without l and r being in the same block can be written

    for (int i=l; i<(c_l+1)*s; ++i) // use s instead of len to be consistent with article        sum += a[i];    for (int k=c_l+1; k<c_r; ++k) // use k for block index to prevent confusion        sum += b[k];    for (int i=c_r*s; i<=r; ++i)        sum += a[i];

Also we set s, both the block size and number of blocks for simplicity, to be ceil(sqrt(n)) so that s*s is >= n? Should be clarified.