Delta Encoding

Problemas de atualização em intervalos

Suponha que você se depare com um problema do seguinte tipo:

Você recebe um vetor v , inicialmente com todos seus números zerados, e q queries. cada query virá representada por 3 inteiros (l,r,x). Ao receber cada query, a mudança esperada é: “Para cada número no vetor, seja i o seu índice. Se l <= i <= r, v[i] deve ter x adicionado ao seu valor. Ao final do programa, deve-se imprimir o vetor todo com seus valores atualizados.

A primeira solução que já vem a cabeça é a seguinte:

int n,q;
	
scanf("%d %d",&n,&q);
vi v(n,0);

for (int i = 0; i < q; ++i){
    int l,r,x;
    scanf("%d %d %d",&l,&r,&x);

    for (int j = l; j <= r; ++j){
        v[j] += x;
    }
}

Nessa solução, para cada uma das q queries, o pior caso seria l = 0 e r = n-1, que faz o laço interno iterar n vezes, o que nos dá uma complexidade O(n*q). Precisamos ser mais rápidos.

Definição

Delta encoding é uma técnica para resolver problemas desse tipo. Precisamos fazer atualizações em intervalos, mas como o vetor só precisa ser visualizado no final, o que fazemos é fazer todas de uma vez só no final. A ideia por trás dessa solução funciona da seguinte forma: Vamos criar um vetor auxiliar delta, que é o vetor que vai acumular as atualizações.

Atualização do intervalo (l,r)

Dessa forma, quando estivermos lendo uma query (l,r,x), faremos o seguinte:

vector<int> delta(n,0);
for(int i = 0; i < q; i++){
    int l,r,x;
    scanf("%d %d %d",&l,&r,&x);
    delta[l] += x;
    delta[r+1] -= x;
}

O trecho de código acima é o delta encoding por si só, o nome é esse porque estamos codificando a informação de que precisamos atualizar aquele intervalo. A parte interessante, é que nesse laço, nossa atualização funciona em O(1).

Obtendo os valores após várias atualizações

Tendo as informações organizadas dessa forma, isso nos permite percorrer o vetor delta da esquerda pra direita obtendo os valores finais do vetor, em O(n).

Isso é feito criando uma variável atual, inicializada com 0. Então, enquanto percorremos o vetor, na i-ésima iteração, sempre somamos a essa variável delta[i], após isso, a configuração final de v[i] será o valor de atual.

Então, é por esse motivo que guardamos a informação daquela forma no vetor. Como vamos percorrer da esquerda pra direita, quando fazemos v[l] += x, estamos dizendo, quando você passar no índice l, você deve adicionar mais x a resposta. E quando fazemos v[r+1] -= x, dizemos: quando seu índice for maior que r, pare de considerar x no resultado.

Dessa forma, a versão final:

vector<int> delta(n+5,0);
vector<int> v(n);

for(int i = 0; i < q; i++){
    int l,r,x;
    scanf("%d %d %d",&l,&r,&x);
    delta[l] += x;
    delta[r+1] -= x;
}

int atual = 0;

for(int i = 0; i < n; i++){
    atual += delta[i];
    v[i] = atual;
}

for(int i = 0; i < n; i++){
    printf("%d ",v[i]);
}
printf("\n");

Ressalvas

Análogo as somas prefixas, mas de forma inversa, essa ED processa atualizações em intervalo muito rapidamente O(1), porém, quando é necessário saber os valores do vetor, e há atualizações pendentes, é necessário percorrer novamente o vetor todo O(n), então essa ED funciona melhor com muitas atualizações e poucas consultas.

Soma de Prefixos

Problemas de consulta em intervalos

Suponha que você se depare com o seguinte problema:

É dado um vetor V, com n números inteiros, em seguida, um número q de consultas que serão feitas nesse vetor. Cada consulta consiste de um par de inteiros (l,r), representando um intervalo, a resposta para cada consulta é a soma dos inteiros nesse intervalo(inclusivo).

Até agora, em qual complexidade sabemos resolver esse problema?

A solução simples seria:

int n;
int q;
cin >> n;
vector<int> v(n);
// leitura dos elementos
for(int i = 0; i < n; i++){
    scanf("%d",v+i);
}
cin >> q;
// respondendo as consultas
for(int i = 0; i < q; i++){
    int l, r;
    scanf("%d %d",&l,&r);
    int soma = 0;
    for(int j = l; j <= r; j++){
        soma += v[j];
    }
    cout << soma << endl;
}

Essa solução teria complexidade O(q*n) aonde q é o número de consultas, e n o tamanho do vetor.

Definição

O vetor de somas prefixas é uma ED que podemos usar para resolver esse tipo de problema de forma mais eficiente. A ideia é construir um vetor P tal que P[i] representa a soma do índice 0 até o índice i.

Tendo essas informações, para responder uma consulta (l,r) podemos usar a seguinte ideia: sabe-se que em P[r] temos a resposta para a consulta (0,r), com isso, podemos agora subtrair a parte que não nos interessa, (0,l-1) ou P[l-1].

Construção

A construção do vetor de somas prefixas em v tem complexidade O(n).

vector<int> psum(v.size(), v[0]);
for(int i = 1; i < v.size(); i++) {
    psum[i] = v[i] + psum[i-1];
}

Resposta de consulta (l,r)

A resposta às consultas tem complexidade constante, já que são só acessos ao vetor. Apenas tem-se que tomar cuidado quando l = 0.

int sum(int l, int r){
    if(l == 0)
        return psum[r];
	else
        return psum[r] - psum[l-1];
}

Ressalvas

Vale lembrar que essa ED é mais interessante de ser usada quando não há (ou há poucas) atualizações nos valores do vetor, caso haja, é necessário recomputar as somas prefixas do vetor todo em O(n), o que não é uma complexidade atrativa.

Além disso, esse raciocínio não precisa se extender apenas a somas, funciona para operações como xor, por exemplo.

Segment Trees

Segment tree (Segtree) é outra estrutura de dados para lidar com problemas de consulta em intervalos. O que tornas as segtrees poderosas é sua capacidade de fazer atualização e consulta em intervalos em complexidade O(log n), além do tipo da consulta ser bem abrangente.

A ideia é a seguinte: Criamos uma árvore, de forma que cada nodo representa a informação que desejamos saber a respeito de um segmento do vetor, e tem dois filhos, um filho representa a metade esquerda desse intervalo, e o outro, a metade direita. Esse processo recursa até que os intervalos atinjam tamanho 1.

Aqui há uma demonstação visual de como funciona: https://visualgo.net/en/segmenttree

É interessante entender o funcionamento da segtree pois, por mais que tenhamos o código pronto, quando mudamos de operação ou precisamos inserir long longs, será necessário mexer na sua estrutura interna.

Representação

Nossa segtree será representada como um vetor. Cada nodo terá um id nesse vetor, e o conteúdo dessa posição representa a informação que aquele nodo guarda. A raiz da segtree será o nodo 0, que guarda a informação sobre o vetor todo. A partir do índice id de um nodo, podemos obter os filhos sem colisões da seguinte forma: índice dos filhos esquerdo e direito são (id*2 + 1,id*2 +2), respectivamente.

    vector<int> st;
    int size;

Operação

Essa função define que informação queremos saber a respeito dos elementos do vetor. Nese caso é uma segtree que computa o máximo de intervalos, mas poderia ser soma, mínimo, produto, xor, gcd, mmc(lcm), or e and lógicos etc.

    int f(int a, int b){
        return max(a,b);
    }

Elemento neutro

O elemento neutro depende da operação. Como queremos saber os máximos, o elemento neutro dessa operação seria um número muito baixo, que nunca será o máximo.

Caso não saiba a definição de elemento neutro, a definição é a seguinte: e é um elemento neutro da operação f se f(e,x) = x para todo x.

Caso fosse uma soma, nosso elemento neutro seria 0, caso fosse um produto, seria 1, etc..

 int el_neutro = -(1e9 + 7);

Consulta

A função recursiva abaixo responde às consultas na segtree. Cada parâmetro tem o seguinte significado:

• sti: id do nodo que estamos na segment tree
• stl: limite inferior do intervalo que aquele nodo representa(inclusivo)
• str: limite superior do intervalo que aquele nodo representa(inclusivo)
• l : limite inferior do intervalo que queremos fazer a consulta
• r : limite superior do intervalo que queremos fazer a consulta

int query(int sti, int stl, int str, int l, int r){
    //O nodo está fora do intervalo que estamos interessados, retorne o elemento neutro que não afeta a consulta
        if(str < l || r < stl) 
            return el_neutro;

    // O nodo está completamente incluído no intervalos que estamos interessados, retorne a informação contida naquele nodo.
        if(stl >= l and str <= r)
            return st[sti];

    // Se chegarmos aqui, é porque esse Nodo está parcialmente contido no intervalo que estamos interessados. Então, continuamos procurando nos filhos.
        int mid = (str+stl)/2;

        return f(query(sti*2+1,stl,mid,l,r),query(sti*2+2,mid+1,str,l,r));
    }

Atualização

Essa função atualiza um elemento da segtree. Cada parâmetro tem o seguinte significado:

• sti: id do nodo que estamos na segment tree
• stl: limite inferior do intervalo que aquele nodo representa(inclusivo)
• str: limite superior do intervalo que aquele nodo representa(inclusivo)
• i : índice do vetor que queremos atualizar
• amm: novo valor daquele índice no vetor

    void update(int sti, int stl, int str, int i, int amm){
        // Chegamos no índice que queremos, vamos atualizar o valor
        if(stl == i and str == i){
            st[sti] = amm;
            return;
        }
        // O intervalo que estamos não contem o índice que queremos atualizar, retorne
        if(stl > i or str < i)
            return;
        
        // O intervalo contém o índice, mas temos que chegar no nodo específico, recurse para os filhos.
        int mid = (stl + str)/2;

        update(sti*2+1,stl,mid,i,amm);
        update(sti*2+2,mid+1,str,i,amm);
        // Após os filhos mais em baixo, precisamos atualizar o valor desse nodo
        st[sti] = f(st[sti*2+1],st[sti*2+2]);
    }

Declaração

Essa é a classe com as funcionalidades implementadas.

class  SegTree{
    vector<int> st;
    int size;

    int el_neutro = -(1e9 + 7);

    int f(int a, int b){
        return max(a,b);
    }

    int query(int sti, int stl, int str, int l, int r){
        if(str < l || r < stl)
            return el_neutro;


        if(stl >= l and str <= r)
            return st[sti];

        int mid = (str+stl)/2;

        return f(query(sti*2+1,stl,mid,l,r),query(sti*2+2,mid+1,str,l,r));
    }

    void update(int sti, int stl, int str, int i, int amm){
        if(stl == i and str == i){
            st[sti] += amm;
            return;
        }

        if(stl > i or str < i)
            return;
        int mid = (stl + str)/2;
        update(sti*2+1,stl,mid,i,amm);
        update(sti*2+2,mid+1,str,i,amm);
        st[sti] = f(st[sti*2+1],st[sti*2+2]);
    }


    public:
        SegTree(int n):  st(4*n,0){size = n;}
        int query(int l, int  r){return query(0,0,size-1,l,r);}
        void update(int i, int amm){update(0,0,size-1,i,amm);}
};

Interface

Os métodos que mostramos são todos internos da segtree, na hora de chama-los, não precisamos passar tantos parâmetros assim.

 public:

        SegTree(int n):  st(4*n,0){size = n;}
        int query(int l, int  r){return query(0,0,size-1,l,r);}
        void update(int i, int amm){update(0,0,size-1,i,amm);}

SegTree

Construtor, recebe o tamanho do vetor.

query

Executa uma consulta, recebe o intervalo(l,r) da consulta, retorna o resultado.

update

Atualiza um índice no vetor recebe o índice e o novo valor.

Construção

vector<int> v;
SegTree st(v.size());
for(int i = 0; i< v.size();i++){
    st.update(i,v[i]);
}

Atualizações em intervalos

A segtree que temos até agora faz atualização de uma posição no vetor e consulta de qualquer em intervalo, em O(log n). Mas e se precisarmos atualizar um intervalo, por exemplo: “Todos os elementos da posição 1 até 10 recebem 2”. Assim, a melhor forma que teríamos de fazer isso seria

SegTree st(n);
// preenche segtree
for(int i = 1 ; i <= 10; i++){
    st.update(i,2);
}

O que tem complexidade O(n * log n). Precisamos fazer isso mais rápido.

Lazy progapation

Lazy propagation é uma alteração na segtree que nos permite fazer atualizações em intervalos em O(log n).

A ideia

Em nossa abordagem anterior, o que tornava a execução lenta é que procurávamos o nodo responsável por cada elemento que precisava ser atualizado.

Para acelerar esse processo, podemos usar uma ideia parecida com a da consulta, em vez de atualizar individualmente os elementos, podemos atualizar a resposta nos intervalos que os contém, e postergar a atualização nos filhos.

Para implementar lazy propagation, cada configuração de segtree vai requerer uma implementação um pouco diferente, por isso, será necessário entender o que cada parte do código está fazendo.

O exemplo a seguir será de uma segtree de soma, aonde a atualização de intervalo vai setar todos os elementos para um qualquer.

vetor de lazy

A ideia é introduzir um vetor extra com o seguinte significado: Quando eu passar no nodo identificado por id, em uma consulta, ou outra atualização, preciso atualizar seu valor para lazy[id]. O vetor has indica se há uma atualização para ser feita naquele nodo.

   vector<int> st;
   vector<int> lazy;
   vector<bool> has;
   int size;

A propagação

A função de propagação é a função que atualiza o valor de um nodo, e posterga a atualização para os filhos. Precisamos chamar essa função toda vez que passamos por algum nodo.

void propagate(int sti, int stl, int str){
       // Se há algo para atualizar, atualize()
       if(has[sti])
           //O valor desse nodo da segtree será (número de elementos que esse intervalo representa vezes novo valor de cada elemento do intervalo)
           st[sti] = lazy[sti] * (str - stl + 1);
           // Se o nó representa um segmento de tamanho maior que 1, isto é, não é terminal, propague a atualização para os filhos.
           if(stl != str){
               lazy[sti*2 + 1] = lazy[sti];
               lazy[sti*2 + 2] = lazy[sti];
               has[sti*2 + 1] = true;
               has[sti*2 + 2] = true;
           }
           // agora não é mais necessário atualizar esse nodo
           has[sti] = false;
       }
   }

A função de atualização em intervalo

Essa é a função que realiza a atualização de intervalos. O significado dos argumentos é:

• sti: id do nodo que estamos na segment tree
• stl: limite inferior do intervalo que aquele nodo representa(inclusivo)
• str: limite superior do intervalo que aquele nodo representa(inclusivo)
• l: limite inferior do intervalo que queremos atualizar no vetor
• r: limite superior do intervalo que queremos atualizar no vetor
• amm: novo valor dos elementos nesse intervalo

    void update_range(int sti, int stl, int str, int l,int r, int amm){
    
        if(stl >= l and str <= r){
            // O valor que será atribuido a todo elemento no intervalo
            lazy[sti] = amm;
            has[sti] = true;
            propagate(sti, stl, str);
            return;
        }

        if(stl > r  or str < l)
            return;

        int mid = (stl + str)/2;

        update_range(sti*2+1,stl,mid,l,r,amm);
        update_range(sti*2+2,mid+1,str,l,r,amm);
        st[sti] = f(st[sti*2+1],st[sti*2+2]);
    }

Versão final

Essa é a versão final da nossa ED.

class  SegTree{
    vector<int> st;
    vector<int> lazy;
    vector<bool> has;
    int size;

    int el_neutro = 0;

    int f(int a, int b){
        return a + b;
    }

     void propagate(int sti, int stl, int str){
        if(has[sti]){
            st[sti] = lazy[sti] * (str - stl + 1);
            if(stl != str){
                lazy[sti*2 + 1] = lazy[sti];
                lazy[sti*2 + 2] = lazy[sti];

                has[sti*2 + 1] = true;
                has[sti*2 + 2] = true;
            }
            has[sti] = false;
        }
    }

    int query(int sti, int stl, int str, int l, int r){
        propagate(sti, stl, str);

        if(str < l || r < stl)
            return el_neutro;


        if(stl >= l and str <= r)
            return st[sti];

        int mid = (str+stl)/2;

        return f(query(sti*2+1,stl,mid,l,r),query(sti*2+2,mid+1,str,l,r));
    }

    void update_range(int sti, int stl, int str, int l,int r, int amm){
    
        if(stl >= l and str <= r){
            lazy[sti] = amm;
            has[sti] = true;
            propagate(sti, stl, str);
            return;
        }

        if(stl > r  or str < l)
            return;
        int mid = (stl + str)/2;
        update_range(sti*2+1,stl,mid,l,r,amm);
        update_range(sti*2+2,mid+1,str,l,r,amm);
        st[sti] = f(st[sti*2+1],st[sti*2+2]);
    }

    public:
        SegTree(int n):  st(4*n,0), lazy(4*n,0),has(4*n,false){size = n;}
        int query(int l, int  r){return query(0,0,size-1,l,r);}
        void update_range(int l, int r, int amm){update_range(0,0,size-1,l,r,amm);}
};

Problemas recomendados

• Compras em FdI
• Produto do Intervalo
• Distinct Characthers
• Cards Sorting
• Ant Colony
• Xenia and Bit Operations
• Consultas Horríveis
• SUM and REPLACE
• Sereja and Brackets
• Kquery
• DQuery

Sparse Table

Nesse tutorial vamos falar sobre uma estrutura de dados chamada Sparse Table, que é uma estrutura de dados poderosa para resolvermos range queries de algumas operações específicas em complexidades superiores as de uma Segment Tree por exemplo.

Por exemplo, uma Sparse Table conseque resolver range minimum(ou maximum) query em O(1), enquanto numa segment tree precisaríamos de O(log n). Outro exemplo poderia ser range query de gcd, numa Segment Tree podemos resolver range queries de GCD em O(log^2 n), já na sparse table conseguimos isso em O(log n). No geral, quando a operação da range query tem uma propriedade chamada idempotência, podemos tirar um log da complexidade usando a Sparse Table.

Idempotência

A propriedade que uma operação precisa ter para que possamos ganhar tempo de execução usando a Sparse Table é a idempotência. Na definição que estamos levando em consideração, uma operação op (binária) é idempotente quando para todo x e todo y, op(x,y) = op(x,op(x,y)). Poderíamos dar uma definição mais precisa porém o que precisamos saber é que numa operação idempotente, aplicar a operação uma vez é o mesmo que aplicar 2,3,4,… qualquer número de vezes maior que 0.

A operação min possui essa propriedade, para qualquer x,y, min(x,y) = min(x,min(x,y)). Outro exemplo é o próprio gcd como mencionado acima. para qualquer x,y, gcd(x,y) = gcd(x,gcd(x,y)).

Mas essa propriedade não é verdade para a operação de soma, por exemplo, seja sum(x,y) = x + y, sum(3,4) != sum(3,sum(3,4)), aplicar a operação mais de uma vez com os mesmos argumentos a direita(ou a esquerda) resulta num resultado diferente, então soma não é idempotente. Na verdade as operações mais comuns vão ser GCD e min/max, mas é importante saber a propriedade para entender porque a ideia que vamos usar funciona e também caso haja uma operação meio maluca que seja idempotente saber se consegue montar a Sparse table sobre ela.

O pulo do gato

Imagine que tenhamos uma função mágica, chamada dp(n,k), que retorna a operação aplicada no intervalo [n, n + (2^k) - 1].

k = 0, [n, n]
k = 1, [n, n + 1]
k = 2, [n, n + 3]
k = 3, [n, n + 7]
.
.

Então se a operação for min, vai ser o mínimo dos elementos nesse intervalo, se for gcd vai ser o gcd entre todos os número desse intervalo etc. Certo então com essa função, vamos fingir que recebemos uma min query para o intervalo [4, 17] em um vetor.

Como a operação é idempotente, podemos fazer o seguinte. A resposta vai ser min(dp(4,3), dp(10,3)),

[0, 1, 2, 3, (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)]
[1, 3, 2, 5, (9, 6, 8, 0, 1, 2, 40, 51,  2,  4, 63, 20,  2,  4)]

O intervalo que estamos interessados está demarcado com um parêntese. Bem, dp(4, 3) = 0, e dp(10,3) = 2, e min(0,2) = 0, que realmente é o mínimo do intervalo. Se a query fosse no intervalo [4,10] poderíamos fazer min(dp(4,2), dp(7,2)), e assim por diante.

Então o que nós estamos fazendo aqui é selecionando uma potencia de dois e duas posições aonde duas chamadas a essa função mágica vão ser suficientes para cobrir exatamente o intervalo que estamos interessados. E a operação precisa ser idempotente porque como estamos selecionando apenas intervalos que tem tamanhos de potências de dois, no caso geral não conseguimos selecionar dois intervalos que não tenham interseção, e caso a operação não seja idempotente, isso fará com que a interseção seja contada duas vezes, fazendo então com que essa ideia não funcione. Voltaremos mais tarde na implementação de como selecionar essas potências.

Então a complexidade que temos até então para resolver consultas é a seguinte: O(k + 2*q) aonde k é o custo da operação, e q é o custo da nossa função mágica. Veremos que conseguimos com programação dinâmica precomputar os valores pra essa função fazendo com que as chamadas a ela tenham tempo constante. Como min() tem tempo constante de gcd() tempo log, é assim que resultamos nas complexidades mencionadas no começo do texto.

Recorrência

Esta é a recorrência da programação dinâmica, nessa recorrência, estamos apenas dizendo o seguinte: O resultado da operação em um intervalo é o resultado da primeira metade combinado com o resultado da segunda metade.

int dp(int i, int k) {
    if(k == 0) {
        return v[i];
    }
    return op(dp(i,k-1),dp(i + (1 << (k-1)). k-1));
}

Versão recursiva

int memo[SIZE][log2(SIZE)+1];
vector<int> v(SIZE);
int dp(int i, int k) {
    if(i >= SIZE) return 0;
    if(k == 0) {
        return v[i];
    }
    if(memo[i][k] != -1) return memo[i][k];
    return memo[i][k] = min(dp(i,k-1),dp(i + (1 << (k-1)), k-1));
}

Versão iterativa

int memo[SIZE][log2(SIZE)+1];
vector<int> v(SIZE);
for(int i = 0; i < SIZE; i++) {
    memo[i][0] = v[i];
}
for(int k = 1; k <= log2(SIZE); k++) {
    for(int i = 0; i < SIZE; i++) {
        if(i + (1 << k -1) >= SIZE) {
            memo[i][k] = memo[i][k-1];
        } else {
            memo[i][k] = op(memo[i][k-1], memo[i + (1 << (k-1))][k-1]);
        }
    }
}

Precisamos apenas computar para potências até log2(SIZE) + 1 porque potências maiores que essa com certeza já são maiores que o vetor.

Outro detalhe de implementação é que temos que tomar cuidado para não acessar fora do vetor, algumas alternativas que temos podem ser por exemplo adicionar um if(i >= SIZE) return 0; na versão recusiva. Na versão iterativa fazemos de maneira análoga.

Estamos preenchendo uma tabela de tamanho O(n log n) aonde n é o tamanho da árvore, para preencher cada célula dessa tabela fazemos operações constantes e uma chamada a op, então a complexidade de montarmos essa tabela para responder as queries é O(n log n * K), aonde K é a complexidade de op.

Ajustando a consulta

Acima demos alguns exemplos de como podemos usar a recorrência que definimos para computar intervalos específicos, por exemplo para [4,17], escolhemos (4,3) e (10,7). O intervalo em questão tem tamanho 14, então a menor potência de 2 que podemos usar para cobri-lo é 8(2^3). Em geral essa menor potência pode ser calculada pela expressão log2(b-a), aonde log2(x) é o chão do logaritmo de x na base 2 e assumimos que b > a.

log2(13) = 3
log2(14) = 3
log2(15) = 3
log2(16) = 4
.
.
.

E sobre as posições da query, a primeira sempre será no começo do intervalo, e a segunda temos que ajustar de forma que o último elemento levado em consideração seja o último.

int query(int a, int b) {
	int lg = log2(b-a);
	return F(tb[a][lg],tb[1 + b-(1 << lg)][lg])
}

Conteúdo complementar

https://www.youtube.com/watch?v=EKcQt-74bNw

Exercícios recomendados