Square Root Decomposition

class SquareRootDecomposition{
    vector<int> nums, blocks;
    int blockSize;

public:
    SquareRootDecomposition(vector<int> &nums){
        this->nums = nums;
        blockSize = sqrt(nums.size()) + 1;
        blocks.resize(blockSize, 0);
        for (int i = 0; i < nums.size(); i++){
            blocks[i / blockSize] += nums[i];
        }
    }

    void update(int index, int value){
        int blockIndex = index / blockSize;
        blocks[blockIndex] += value - nums[index];
        nums[index] = value;
    }

    int query(int left, int right)
    {
        int sum = 0;
        int startBlock = left / blockSize;
        int endBlock = right / blockSize;

        // same blocks
        if (startBlock == endBlock){
            for (int i = left; i <= right; i++){
                sum += nums[i];
            }
            return sum;
        }

        // Left partial block
        for (int i = left; i < (startBlock + 1) * blockSize; i++){
            sum += nums[i];
        }

        // Complete blocks
        for (int i = startBlock + 1; i < endBlock; i++){
            sum += blocks[i];
        }

        // Right partial block
        for (int i = endBlock * blockSize; i <= right; i++){
            sum += nums[i];
        }
        return sum;
    }
};