Sqrt Tree

Seja uma array $a$ contendo $n$ elementos e a operação "$\circ$" que satisfaz a propriedade associativa: $(x \circ y) \circ z = x \circ (y \circ z)$ é verdadeiro para qualquer $x$, $y$, $z$.

Portanto, operações como $\ gcd/mdc$, $\min$, $\max$, $+$, $\text{and}$, $\text{or}$, $\text{xor}$, etc. satisfazem essas condições.

Também temos algumas consultas $q(l, r)$. Para cada consulta, precisamos calcular $a_l \circ a_{l+1} \circ \dots \circ a_r$.

A Sqrt Tree pode processar essas consultas em tempo $O(1)$ com tempo $O(n \cdot \log \log n)$ de pré-processamento e memória $O(n \cdot \log \log n)$.

Descrição

Construção da sqrt decomposition

Vamos fazer uma sqrt decomposition. Dividimos nossa array em $\sqrt{n}$ blocos, cada bloco tem tamanho $\sqrt{n}$. Para cada bloco, calculamos:

  1. Respostas às consultas que estão no bloco e começam no início do bloco ($\text{prefixOp}$)
  2. Respostas às consultas que estão no bloco e terminam no final do bloco ($\text{suffixOp}$)

E calcularemos uma array adicional:

  1. $\text{between}_{i, j}$ (para $i \le j$) - responde a consulta que começa no início do bloco $i$ e termina no final do bloco $j$. Observe que temos $\sqrt{n}$ blocos, portanto o tamanho dessa array será $O(\sqrt{n}^2) = O(n)$.

Vamos ver o exemplo.

Deixe que "$\circ$" seja $+$ (calculamos a soma em um segmento) e temos a seguinte array $a$:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

Ele será dividido em três blocos: {1, 2, 3}, {4, 5, 6} e {7, 8, 9}.

Para o primeiro bloco, $\text{prefixOp}$ é {1, 3, 6} e $\text{suffixOp}$ será {6, 5, 3}.(6, 6-1, 6-(1+2))

Para o segundo bloco, $\text{prefixOp}$ é {4, 9, 15} e $\text{suffixOp}$ será {15, 11, 6}.

Para o terceiro bloco, $\text{prefixOp}$ é {7, 15, 24} e $\text{suffixOp}$ será {24, 17, 9}.

a array $\text{between}$ será:

{
    {6, 21, 45},
    {0, 15, 39},
    {0, 0,  24}
}

(assumimos que elementos inválidos em que $i > j$ sejam preenchidos com zeros)

É óbvio ver que essas arrays podem ser facilmente calculadas em tempo e memória linear $O(n)$.

Já podemos responder a algumas consultas usando essas arrays. Se a consulta não couber em um bloco, podemos dividi-la em três partes: sufixo de um bloco, algum segmento de blocos contínuos e o prefixo de algum bloco. Podemos responder a uma consulta dividindo-a em três partes e obtendo nossa operação de algum valor de $\text{suffixOp}$, depois, de algum valor de $\text{b}$, e assim algum valor de $\text{prefixOp}$.

Mas se tivermos consultas que se encaixam totalmente em um bloco, não podemos processá-las usando essas três arrays.

Construindo uma árvore

Não podemos responder apenas às consultas que se encaixam inteiramente em um bloco. Entretanto, podemos construir a mesma estrutura descrita acima para cada bloco. E fazemos isso recursivamente, até atingirmos o tamanho do bloco de $1$ ou $2$. As respostas para esses blocos podem ser calculadas facilmente em $O(1)$.

Então, nós temos uma árvore. Cada nó da árvore representa algum segmento da array. O nó que representa o segmento da array com tamanho $k$ tem $\sqrt{k}$ filhos -- para cada bloco. Além disso, cada nó contém as três arrays descritas acima para o segmento contido. A raiz da árvore representa toda a array. Nós com comprimentos de segmento $1$ ou $2$ são folhas.

A altura dessa árvore é $O(\log \log n)$, porque se algum vértice da árvore representar uma array com comprimento $k$, seus filhos terão comprimento $\sqrt{k}$. $\log(\sqrt{k}) = \frac{\log{k}}{2}$, então $\log k$ diminui duas vezes a cada camada da árvore e, portanto, sua altura é $O(\log \log n)$. O tempo para construção e uso da memória será $O(n \cdot \log \log n)$, porque todos os elementos da array aparecem exatamente uma vez em cada camada da árvore.

Agora podemos responder às consultas em $O(\log \log n)$. Podemos descer na árvore até encontrarmos um segmento com comprimento $1$ ou $2$ (a resposta pode ser calculada em tempo $O(1)$) ou encontrar o primeiro segmento no qual nossa consulta não se encaixa totalmente.

Agora conseguimos $O(\log \log n)$ por consulta.

Otimizando a complexidade da consulta/query

Uma das otimizações mais óbvias é fazer uma busca binária no nó da árvore que precisamos. Usando binary search podemos alcançar a complexidade $O(\log \log \log n)$ por query. Podemos fazer isso ainda mais rápido.

Vamos assumir que:

  1. Cada tamanho de bloco é uma potência de dois.
  2. Todos os blocos são iguais em cada camada.

Para alcançar isso, podemos adicionar alguns elementos zero à nossa array para que seu tamanho se torne uma potência de dois.

Quando usamos isso, alguns tamanhos de bloco podem se tornar duas vezes maiores para ter uma potência de dois, mas ainda tem $O(\sqrt{k})$ em tamanho e mantemos a complexidade linear para criar as arrays em um segmento.

Agora, podemos verificar facilmente se a consulta se encaixa inteiramente em um bloco com tamanho $2^k$. Vamos escrever os intervalos da consulta, $l$ e $r$ em formato binário. Por exemplo, vamos supor que $k=4, l=39, r=46$. A representação binária de $l$ e $r$ é:

$l = 39_{10} = 100111_2$

$r = 46_{10} = 101110_2$

Lembre-se de que uma camada contém segmentos do mesmo tamanho e o bloco de uma camada também tem o mesmo tamanho (no nosso caso, o tamanho é de $2^k = 2^4 = 16$. Os blocos cobrem a array inteira, então o primeiro bloco cobre os elementos $(0 - 15)$ ($(000000_2 - 001111_2)$ em binário), o segundo cobre os elementos $(16 - 31)$ ($(010000_2 - 011111_2)$ em binário) e assim por diante. Podemos ver que os índices das posições cobertas por um bloco podem diferir apenas em $k$ (no nosso caso: $4$) últimos bits. No nosso caso $l$ e $r$ tem bits iguais exceto os 4 finais, então eles pertencem em um bloco.

Portanto, precisamos verificar se nada mais que $k$ bits diferem (ou $l\ \text{xor}\ r$ não exceda $2^k-1$).

Usando esta observação, podemos encontrar uma camada que é adequada para responder à consulta rapidamente.

  1. Para cada $i$ que não exceda o tamanho da array, encontramos o maior bit igual a $1$. Para fazer isso rapidamente, usamos DP e uma array pré-calculada.

  2. Agora, para cada $q(l, r)$ encontramos o maior bit de $l\ \text{xor}\ r$ e, usando essas informações, é fácil escolher a camada na qual podemos processar a consulta facilmente. Também podemos usar uma array pré-calculada aqui.

Para mais detalhes, consulte o código abaixo.

Portanto, usando isso, podemos responder às consultas em $O(1)$ cada. Viva! :)

Atualizando elementos

Também podemos atualizar elementos na Sqrt Tree. Ambas as atualizações (de elemento único e as de segmento) são suportadas.

Atualizando um único elemento

Considere uma query $\text{update}(x, val)$ que faça a atribuição $a_x = val$. Precisamos executar essa query com rapidez suficiente.

Abordagem trivial

Primeiro, vamos dar uma olhada no que é alterado na árvore quando um único elemento é alterado. Considere um nó de árvore com comprimento $l$ e suas arrays: $\text{prefixOp}$, $\text{suffixOp}$ e $\text{between}$. Apenas $O(\sqrt{l})$ elementos de $\text{prefixOp}$ e $\text{suffixOp}$ mudam (apenas dentro do bloco com o elemento alterado). $O(l)$ elementos são alterados em $\text{between}$. Portanto, $O(l)$ elementos no nó da árvore são atualizados.

Lembrando que qualquer elemento $x$ é presente exatamente em um nó da árvore em cada camada. O nó raiz (camada $0$) tem comprimento $O(n)$, os nós da camada $1$ têm comprimento $O(\sqrt{n})$, nós da camada $2$ têm comprimento $O(\sqrt{\sqrt{n}})$, etc. Então a complexidade de tempo por atualização é $O(n + \sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(n)$.

Mas ainda é muito lento. Isso pode ser feito mais rápido.

Uma sqrt-tree dentro da sqrt-tree

Para otimizar a árvore, vamos nos livrar da array between. Em vez da array $\text{between}$, armazenamos outra sqrt-tree para o nó raiz. Vamos chamá-la de $\text{index}$. Ele desempenha o mesmo papel que $\text{between}$— responde às consultas nos segmentos de blocos. Observe que o restante dos nós da árvore não possuem $\text{index}$, eles mantém a array $\text{between}$.

Uma sqrt-tree é indexada, se o seu nó raiz tiver um $\text{index}$. Uma sqrt-tree com uma array $\text{between}$ em seu nó raiz é unindexada. Observe que $\text{index}$ é unindexado.

Portanto, temos o seguinte algoritmo para atualizar uma árvore indexada :

Observe que a complexidade da query ainda é $O(1)$: precisamos usar $\text{index}$ na query não mais que uma vez, e isso levará tempo $O(1)$.

Portanto, a complexidade do tempo total para atualizar um único elemento é $O(\sqrt{n})$. Hooray! :)

Atualizando um segmento

Sqrt-tree também pode atribuir um valor em um segmento inteiro. $\text{massUpdate}(x, l, r)$ significa: $a_i = x$ em todo $l \le i \le r$.

Existem duas abordagens para fazer isso: uma delas executa o $\text{massUpdate}$ em $O(\sqrt{n}\cdot \log \log n)$, mantendo $O(1)$ por query/consulta. O segundo executa o $\text{massUpdate}$ in $O(\sqrt{n})$, mas a complexidade da consulta se torna $O(\log \log n)$.

Faremos uma "lazy propagation" da mesma maneira que é feita na árvore segmentária: marcamos alguns nós como lazy, o que significa que iremos "puxá-los" quando necessário. Mas uma coisa é diferente das árvores de segmentos: puxar um nó é caro, portanto, isso não pode ser feito em consultas. Na camada $0$, puxar um nó leva tempo $O(\sqrt{n})$. Portanto, não puxamos nós em consultas, apenas examinamos se o nó atual ou se seu parente são "lazy", e apenas o levamos em consideração durante a execução de consultas.

Primeira abordagem

Na primeira abordagem, dizemos que apenas os nós da camada $1$ (com tamanho $O(\sqrt{n}$) podem ser lazy. Ao puxar esse nó, ele atualiza toda a sua subárvore(incluindo ele mesmo) em $O(\sqrt{n}\cdot \log \log n)$. O processo de $\text{massUpdate}$ é feito da seguinte forma:

Então, podemos executar o $\text{massUpdate}$ rápido. Mas como lazy propagation afeta as consultas? Elas terão as seguintes modificações:

A complexidade da consulta ainda permanece $O(1)$.

Segunda abordagem

Nesta abordagem, cada nó pode ser lazy (exceto a raiz). Até os nós em $\text{index}$ podem ser lazy. Portanto, durante o processamento de uma consulta, precisamos procurar pelas tags com lazy em todos os nós parentes, ou seja, a complexidade da consulta será $O(\log \log n)$.

Porém, $\text{massUpdate}$ se torna rápido. Parece da seguinte maneira:

Observe que, quando fazemos a chamada recursiva, fazemos o prefixo ou o sufixo $\text{massUpdate}$. Porém, para atualizações de prefixo e sufixo, não podemos ter mais do que um filho parcialmente coberto. Então, visitamos um nó na camada $1$, dois nós na camada $2$ e dois nós em qualquer camada mais profunda. Portanto, a complexidade do tempo é $O(\sqrt{n} + \sqrt{\sqrt{n}} + \dots) = O(\sqrt{n})$. A abordagem aqui é semelhante à atualização em massa da árvore segmentária.

Implementação

A seguinte implementação da Sqrt Tree pode executar as seguintes operações: construir em $O(n \cdot \log \log n)$, responder consultas em $O(1)$ e atualizar um elemento em $O(\sqrt{n})$.

SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);

inline int log2Up(int n) {
    int res = 0;
    while ((1 << res) < n) {
        res++;
    }
    return res;
}

class SqrtTree {
private:
    int n, lg, indexSz;
    vector<SqrtTreeItem> v;
    vector<int> clz, layers, onLayer;
    vector< vector<SqrtTreeItem> > pref, suf, between;

    inline void buildBlock(int layer, int l, int r) {
        pref[layer][l] = v[l];
        for (int i = l+1; i < r; i++) {
            pref[layer][i] = op(pref[layer][i-1], v[i]);
        }
        suf[layer][r-1] = v[r-1];
        for (int i = r-2; i >= l; i--) {
            suf[layer][i] = op(v[i], suf[layer][i+1]);
        }
    }

    inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
        int bSzLog = (layers[layer]+1) >> 1;
        int bCntLog = layers[layer] >> 1;
        int bSz = 1 << bSzLog;
        int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
        for (int i = 0; i < bCnt; i++) {
            SqrtTreeItem ans;
            for (int j = i; j < bCnt; j++) {
                SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
                ans = (i == j) ? add : op(ans, add);
                between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
            }
        }
    }

    inline void buildBetweenZero() {
        int bSzLog = (lg+1) >> 1;
        for (int i = 0; i < indexSz; i++) {
            v[n+i] = suf[0][i << bSzLog];
        }
        build(1, n, n + indexSz, (1 << lg) - n);
    }

    inline void updateBetweenZero(int bid) {
        int bSzLog = (lg+1) >> 1;
        v[n+bid] = suf[0][bid << bSzLog];
        update(1, n, n + indexSz, (1 << lg) - n, n+bid);
    }

    void build(int layer, int lBound, int rBound, int betweenOffs) {
        if (layer >= (int)layers.size()) {
            return;
        }
        int bSz = 1 << ((layers[layer]+1) >> 1);
        for (int l = lBound; l < rBound; l += bSz) {
            int r = min(l + bSz, rBound);
            buildBlock(layer, l, r);
            build(layer+1, l, r, betweenOffs);
        }
        if (layer == 0) {
            buildBetweenZero();
        } else {
            buildBetween(layer, lBound, rBound, betweenOffs);
        }
    }

    void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
        if (layer >= (int)layers.size()) {
            return;
        }
        int bSzLog = (layers[layer]+1) >> 1;
        int bSz = 1 << bSzLog;
        int blockIdx = (x - lBound) >> bSzLog;
        int l = lBound + (blockIdx << bSzLog);
        int r = min(l + bSz, rBound);
        buildBlock(layer, l, r);
        if (layer == 0) {
            updateBetweenZero(blockIdx);
        } else {
            buildBetween(layer, lBound, rBound, betweenOffs);
        }
        update(layer+1, l, r, betweenOffs, x);
    }

    inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
        if (l == r) {
            return v[l];
        }
        if (l + 1 == r) {
            return op(v[l], v[r]);
        }
        int layer = onLayer[clz[(l - base) ^ (r - base)]];
        int bSzLog = (layers[layer]+1) >> 1;
        int bCntLog = layers[layer] >> 1;
        int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
        int lBlock = ((l - lBound) >> bSzLog) + 1;
        int rBlock = ((r - lBound) >> bSzLog) - 1;
        SqrtTreeItem ans = suf[layer][l];
        if (lBlock <= rBlock) {
            SqrtTreeItem add = (layer == 0) ? (
                query(n + lBlock, n + rBlock, (1 << lg) - n, n)
            ) : (
                between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
            );
            ans = op(ans, add);
        }
        ans = op(ans, pref[layer][r]);
        return ans;
    }
public:
    inline SqrtTreeItem query(int l, int r) {
        return query(l, r, 0, 0);
    }

    inline void update(int x, const SqrtTreeItem &item) {
        v[x] = item;
        update(0, 0, n, 0, x);
    }

    SqrtTree(const vector<SqrtTreeItem>& a)
        : n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
        clz[0] = 0;
        for (int i = 1; i < (int)clz.size(); i++) {
            clz[i] = clz[i >> 1] + 1;
        }
        int tlg = lg;
        while (tlg > 1) {
            onLayer[tlg] = (int)layers.size();
            layers.push_back(tlg);
            tlg = (tlg+1) >> 1;
        }
        for (int i = lg-1; i >= 0; i--) {
            onLayer[i] = max(onLayer[i], onLayer[i+1]);
        }
        int betweenLayers = max(0, (int)layers.size() - 1);
        int bSzLog = (lg+1) >> 1;
        int bSz = 1 << bSzLog;
        indexSz = (n + bSz - 1) >> bSzLog;
        v.resize(n + indexSz);
        pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
        suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
        between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
        build(0, 0, n, 0);
    }
};

Problemas

CodeChef - SEGPROD