Mo's algorithm (qsrd)

struct query
{
    int l, r, idx;
};

std::vector<long long> Mo(std::vector<int> &data, std::vector<query> &queries)
{
    static int square;
    square = sqrt(data.size());
    std::vector<long long> answers(queries.size(), 0);

    // Sort queries into blocks
    std::sort(queries.begin(), queries.end(), [](query l, query r) -> bool
    {
        if(l.l / square != r.l / square)
            return l.l / square < r.l / square;

        return l.r < r.r;
    });

    int l = 0, r = 0;
    long long sum = 0;

    // Process subsequent blocks of queries
    for(query &q : queries)
    {
        while(l < q.l)     sum -= data[l++];
        while(l > q.l)     sum += data[--l];
        while(r <= q.r)    sum += data[r++];
        while(r > q.r + 1) sum -= data[--r];

        answers[q.idx] = sum;
    }

    return answers;
}