Sqrt Decomposition

Sqrt Decomposition é um método (ou uma estrutura de dados) que permite executar algumas operações comuns (encontrar a soma dos elementos da sub-array, encontrar o elemento mínimo/máximo etc.) com $O(\sqrt n)$ operações, que é bem mais rápido que $O(n)$ para o algoritmo trivial.

Primeiro, descrevemos a estrutura de dados para uma das aplicações mais simples dessa idéia, depois mostramos como generalizá-la para resolver alguns outros problemas e, finalmente, analisamos um uso ligeiramente diferente dessa idéia: decompor as solicitações de entrada em blocos.

Estrutura de dados baseada em uma Sqrt-decomposition

Seja uma array $a[0 \dots n-1]$, implemente uma estrutura de dados que permita encontrar a soma dos elementos $a[l \dots r]$ para um arbitrário $l$ e $r$ em $O(\sqrt n)$.

Descrição

A idéia básica da sqrt decomposition é o pré-processamento. Dividiremos a array $a$ em blocos de tamanho aproximadamente $\sqrt n$, e, para cada bloco $i$ pré-calcularemos a soma dos elementos nele $b[i]$.

Podemos assumir que o tamanho do bloco e o número de blocos sejam iguais a $\sqrt n$(arredondado):

$$ s = \lceil \sqrt n \rceil $$

Em seguida, a array $a$ é dividida em blocos da seguinte maneira:

$$ \underbrace{a[0], a[1], \dots, a[s-1]}_{\text{b[0]}}, \underbrace{a[s], \dots, a[2s-1]}_{\text{b[1]}}, \dots, \underbrace{a[(s-1) \cdot s], \dots, a[n]}_{\text{b[s-1]}} $$

O último bloco pode ter menos elementos que os outros (se $n$ não for um múltiplo de $s$), não é importante para a discussão (pois pode ser tratado com facilidade). Assim, para cada bloco $k$, sabemos a soma dos elementos nele: $b[k]$:

$$ b[k] = \sum\limits_{i=k\cdot s}^{\min {(n-1,(k+1)\cdot s - 1})} a[i] $$

Portanto, calculamos os valores de $b[k]$ (isso exige $O(n)$ operações). Como eles podem nos ajudar a responder as consultas $[l; r]$ ? Observe que se o intervalo $[l; r]$ for longo o bastante, conterá vários blocos inteiros e, para esses blocos, podemos encontrar a soma dos elementos neles em uma única operação. Como resultado, o intervalo $[l; r]$ conterá partes de apenas dois blocos, e teremos que calcular a soma dos elementos nessas partes trivialmente.

Assim, para calcular a soma dos elementos no intervalo $[l; r]$ precisamos somar os elementos das duas "caudas": $[l\dots (k + 1)\cdot s-1]$ e $[p\cdot s\dots r]$ , e somar os valores $b[i]$ em todos os blocos de $k + 1$ até $p-1$:

$$ \sum\limits_{i=l}^r a[i] = \sum\limits_{i=l}^{(k+1) \cdot s-1} a[i] + \sum\limits_{i=k+1}^{p-1} b[i] + \sum\limits_{i=p\cdot s}^r a[i] $$

Nota: quando $k = p$, ou seja, $l$ e $r$ pertencem ao mesmo bloco, a fórmula não pode ser aplicada e a soma deve ser calculada trivialmente.

Essa abordagem nos permite reduzir significativamente o número de operações. De fato, o tamanho de cada "cauda" não excede o comprimento $s$ do bloco, e o número de blocos na soma não excede $s$. Como escolhemos $s \approx \sqrt n$, o número total de operações necessárias para encontrar a soma dos elementos no intervalo $[l; r]$ é $O(\sqrt n)$.

Implementação

Implementação mais simples:

// input
int n;
vector<int> a (n);

// pré-processamento
int len = (int) sqrt (n + .0) + 1; // tamanho do bloco e número de blocos
vector<int> b (len);
for (int i=0; i<n; ++i)
    b[i / len] += a[i];

// consultas/queries
for (;;) {
    int l, r;
  // ler input para a próxima consulta
    int sum = 0;
    for (int i=l; i<=r; )
        if (i % len == 0 && i + len - 1 <= r) {
            // se o bloco inteiro começando de i pertencer ao intervalo [l; r]
            sum += b[i / len];
            i += len;
        }
        else {
            sum += a[i];
            ++i;
        }
}

Essa implementação possui muitas operações de divisão (que são muito mais lentas que outras operações aritméticas). Em vez disso, podemos calcular os índices dos blocos $c_l$ e $c_r$ que possuem índices $l$ e $r$, e percorrer sobre os blocos $c_l+1 \dots c_r-1$ com um processamento separado das "caudas" nos blocos $c_l$ e $c_r$. Essa abordagem corresponde à última fórmula na descrição e torna o caso $c_l = c_r$ um caso especial.

int sum = 0;
int c_l = l / len,   c_r = r / len;
if (c_l == c_r)
    for (int i=l; i<=r; ++i)
        sum += a[i];
else {
    for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
        sum += a[i];
    for (int i=c_l+1; i<=c_r-1; ++i)
        sum += b[i];
    for (int i=c_r*len; i<=r; ++i)
        sum += a[i];
}

Outros problemas

Até agora estávamos discutindo o problema de encontrar a soma dos elementos de uma subarray contínua. Esse problema pode ser estendido para permitir a atualização individual dos elementos na array. Se um elemento $a[i]$ for alterado, o valor de $b[k]$ precisa ser atualizado para o bloco no qual o elemento pertence ($k = i / s$) em uma operação:

$$ b[k] += a_{novo}[i] - a_{antigo}[i] $$

Por outro lado, a tarefa de encontrar a soma dos elementos pode ser substituída pela tarefa de encontrar o elemento mínimo / máximo de uma subarray. Se esse problema também precisar abordar as atualizações de elementos individuais, também é possível atualizar o valor de $b[k]$, mas será necessário iterar por todos os valores do bloco $k$ em $O(s) = O(\sqrt{n})$ operações.

Sqrt decomposition pode ser aplicada de maneira semelhante em outros problemas: fencontrar o número de elementos zero, encontrar o primeiro elemento diferente de zero, contar elementos que satisfazem uma determinada propriedade, etc.

Outra classe de problemas aparece quando precisamos atualizar os elementos da array em intervalos: incrementar elementos existentes ou substituí-los por um determinado valor.

Por exemplo, podemos realizar dois tipos de operações em uma array: adicionar um determinado valor $\delta$ para todos os elementos da array no intervalo $[l; r]$ ou consultar o valor do elemento $a[i]$. Vamos armazenar o valor que deve ser adicionado a todos os elementos do bloco $k$ em $b[k]$ (inicialmente todos os $b[k] = 0$). Durante cada operação "add", precisamos adicionar $\delta$ em $b[k]$ para todos os blocos que pertencem ao intervalo $[l; r]$ e adicionar $\delta$ em $a[i]$ para todos os elementos que pertencem às "caudas" do intervalo. A resposta de uma consulta $i$ é simplesmente $a[i] + b[i/s]$. Dessa forma, a operação "add" possui complexidade $O(\sqrt{n})$, e responder a uma consulta tem complexidade $O(1)$.

Finalmente, essas duas classes de problemas podem ser combinadas se a tarefa exigir que ambas altualizações de elementos e consultas/queries sejam em um intervalo. Ambas as operações podem ser feitas com complexidade $O(\sqrt{n})$. Isso exigirá dois blocos de array $b$ e $c$: uma para acompanhar as atualizações dos elementos e outra para acompanhar as respostas da consulta/query.

Existem outros problemas que podem ser resolvidos usando sqrt decomposition, por exemplo, um problema sobre manter um conjunto de números que permitiria adicionar / excluir números, verificar se um número pertence ao conjunto e encontrar o $k$-ésimo maior número. Para resolvê-lo, é necessário armazenar números em ordem crescente, dividir em vários blocos com $\sqrt{n}$ números em cada bloco. Toda vez que um número é adicionado / excluído, os blocos precisam ser reequilibrados movendo-se os números entre o início e o fim dos blocos adjacentes.

Algoritmo de Mo

Uma idéia similar, baseada na sqrt decomposition, pode ser usada para responder a consultas de intervalo(range queries) ($Q$) offline em $O((N+Q)\sqrt{N})$. Isso pode parecer pior do que os métodos da seção anterior, pois essa é uma complexidade um pouco pior do que tínhamos anteriormente e o fato de não podermos atualizar valores entre duas consultas. Mas em muitas situações esse método tem vantagens. Durante uma sqrt decomposition, temos que pré-calcular as respostas para cada bloco e mesclá-las para obter as respostas da consulta/query. Em alguns problemas, essa etapa de mesclagem pode ser bastante problemática. Por exemplo, quando cada consulta pergunta qual a moda do intervalo (o número que aparece com maior frequência). Para isso, cada bloco teria que armazenar a contagem de cada número nele em algum tipo de estrutura de dados, e não podemos mais executar a etapa de mesclagem com rapidez suficiente. O algoritmo de Mo usa uma abordagem completamente diferente, que pode responder a esse tipo de consulta rapidamente, porque mantém o controle de apenas uma estrutura de dados e as únicas operações com ela são fáceis e rápidas.

A idéia é responder às consultas em uma ordem especial com base nos índices. Primeiro, responderemos a todas as consultas que tem o índice esquerdo no bloco 0, depois responderemos a todas as consultas que tem o índice esquerdo no bloco 1 e assim por diante. E também teremos que responder às consultas de um bloco em uma ordem especial, ordenado pelo índice/index direito das consultas.

Usaremos uma única estrutura de dados. Essa estrutura de dados armazenará informações sobre o intervalo. No início, esse intervalo estará vazio. Quando queremos responder à próxima consulta (na ordem especial), simplesmente aumentamos ou reduzimos o intervalo adicionando ou removendo elementos nos dois lados do intervalo atual, até transformá-lo no intervalo de consulta. Dessa maneira, precisamos apenas adicionar ou remover um único elemento por vez, o que deve ser uma operação simples na estrutura de dados.

Como alteramos a ordem de responder as consultas/queries, isso só é possível quando é permitido responder às consultas no modo offline.

Implementação

No algoritmo de Mo, usamos duas funções para adicionar um índice e remover um índice do intervalo que estamos mantendo no momento.

void remove(idx);  // remover valor no indice(idx) da estrutura de dados
void add(idx);     // adicionar valor no indice(idx) da estrutura de dados
int get_answer();  // extrair a resposta atual da estrutura de dados

int block_size;

struct Query {
    int l, r, idx;
    bool operator<(Query other) const
    {
        return make_pair(l / block_size, r) <
               make_pair(other.l / block_size, other.r);
    }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    // inicializar a estrutura de dados

    int cur_l = 0;
    int cur_r = -1;
    // intervalo [cur_l, cur_r]
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer();
    }
    return answers;
}

Com base no problema, podemos usar uma estrutura de dados diferente e modificar as funções add/remove/get_answer. Por exemplo, se for pedido para encontrar consultas de soma de intervalo(range sum queries), usamos um número inteiro simples na estrutura de dados, que é $0$ no começo. A função add simplesmente adiciona o valor da posição e, posteriormente, atualiza a variável de resposta. A função remove irá subtrair o valor e, da mesma maneira, atualiza a variável da resposta. E get_answer apenas retorna o inteiro.

Para responder as consultas/queries de moda, podemos usar uma árvore de pesquisa binária(binary search tree) (por exemplo: map<int, int>) para armazenar com que frequência cada número aparece no intervalo atual e uma segunda árvore de pesquisa binária (por exemplo: set<pair<int, int>>) para manter as contagens dos números (pares contagem-número) em ordem. O método add remove o número atual da segunda BST, incrementa a contagem na primeira, e insere o número de volta na segunda BST. remove faz a mesma coisa, apenas decrementa a contagem. E get_answer apenas verifica a segunda árvore e retorna o melhor valor em $O(1)$.

Complexidade

Ordenar todas as queries/consultas levará $O(Q \log Q)$.

E as outras operações? Quantas vezes add e remove serão chamadas?

Assumindo que o tamanho do bloco seja $S$.

Chamaremos add(cur_r) e remove(cur_r) apenas $O(N)$ vezes para todas essas consultas combinadas. Isso nos dará $O(\frac{N}{S} N)$ chamadas para todos os blocos.

O valor de cur_l pode mudar no máximo $O(S)$ vezes entre duas consultas durante a execução. Portanto, temos um adicional de $O(S Q)$ chamadas para add(cur_l) e remove(cur_l).

Para $S \approx \sqrt{N}$ isso nos dá $O((N + Q) \sqrt{N})$ operações no total. Portanto, a complexidade é $O((N+Q)F\sqrt{N})$ onde $O(F)$ é a complexidade das funções add e remove.

Dicas para melhorar o tempo de execução

bool cmp(pair<int, int> p, pair<int, int> q) {
    if (p.first / BLOCK_SIZE != q.first / BLOCK_SIZE)
        return p < q;
    return (p.first / BLOCK_SIZE & 1) ? (p.second < q.second) : (p.second > q.second);
}

Você pode ler sobre uma abordagem de ordenação mais rápida aqui.

Problemas