Estrutura de dados para atualizações em intervalos e consulta de número de zeros

13

Estou procurando uma estrutura de dados que mantenha uma tabela inteira t de tamanho n e permita as seguintes operações no tempo O(logn) .

  • increase(a,b) , que aumentat[a],t[a+1],,t[b] .
  • , que diminui t [ a ] , t [ a + 1 ] , , t [ b ] .decrease(a,b)t[a],t[a+1],,t[b]
  • , que retorna o número de índices i tal que t [ i ] 0 .support()Eut[Eu]0 0

Você tem a promessa de que cada chamada para diminuir pode ser correspondida a uma chamada anterior para aumentar com os mesmos parâmetros . A aplicação que tenho em mente é um algoritmo de linha de varredura para calcular no tempo O ( n log n ) a área da união de n dados retângulos retilíneos.uma,bO(nregistron)

Uma árvore quádrupla teria tamanho , portanto não é uma solução. As árvores Fenwick ou Interval têm o sabor certo, mas não vejo como estendê-las para apoiar as operações acima.Θ(n2)

Christoph Dürr
fonte
As árvores Fenwick não usariam a promessa de que "cada chamada para diminuir pode ser correspondida a uma chamada anterior para aumentar com os mesmos parâmetros a, b"; portanto, pode haver uma solução mais simples usando essa promessa (mas ela me escapa por enquanto).
Jeremy
Como o número de entradas que você pode ter é no máximo (é possível detectar repetições e não inserir na estrutura de dados), ainda obtemos desempenho O ( log n ) usando a estrutura de dados da árvore de medidas comuns. Veja cosy.sbg.ac.at/~ksafdar/data/courses/SeminarADS/… slide 47-52. n2O(registron)
Chao Xu
Jérémie e Chao Xu. Obrigado por seus comentários. Agora eu entendo como a Árvore Interval pode ser usada para manter o comprimento total da união de um conjunto de intervalos em mudança. Esta é de fato uma estrutura de dados muito fofa.
Christoph Dürr 12/04
Para o problema geral da estrutura de dados, a busca no tempo do requer espaço O ( p ) O ( n 2 ) onde p é o tamanho da lista de pares de coordenadas ativas. Mas, de fato, para o algoritmo sweepline p O ( n ) , o espaço permanece linear. O problema ainda está aberto para uma estrutura de dados com espaço melhor que O ( p ) , quando pregistro(n2)O(registro(n))O(p)O(n2)ppO(n)O(p) . pω(n)
Jeremy
2
Aqui está um link agradável, onde você pode testar suas implementações contra outras soluções para o mesmo problema: spoj.com/OI/problems/NKMARS
Erel Segal-Halevi

Respostas:

2

Use uma árvore de segmentos - uma partição recursiva do intervalo em intervalos menores. Cada intervalo [ a , b ] de suas operações de atualização pode ser particionado em O ( log n ) dos intervalos nessa partição recursiva. Para cada intervalo [ x , y ] de armazenamento:[1,n][uma,b]O(registron)[x,y]

  • O número de intervalos [c(x,y) que foram aumentados e não diminuídos, de modo que [ x , y ] é um dos intervalos nos quais [ a , b ] é particionado[uma,b][x,y][uma,b]
  • O número de células que não são cobertas por subconjuntos particionados de intervalos que estão em [ x , y ] ou menos na recursãovocê(x,y)[x,y]

Então, se é dividido recursivamente em [ x , z ] e [ z + 1 , w ] , temos u ( x , y ) = { 0 se  c ( x , y ) > 0 u ( x , z ) + u ( z + 1 , y ) caso contrário[x,y][x,z][z+1,W]

você(x,y)={0 0E se c(x,y)>0 0você(x,z)+você(z+1,y)de outra forma
para que possamos atualizar cada valor de em tempo constante quando os outros dados de um intervalo mudam. Cada consulta de suporte pode ser respondida olhando para u ( 1 , n ) .você(x,y)você(1,n)

Para executar uma operação de aumento , particione [ a , b ] em intervalos O ( log n ) , incremente c ((uma,b)[uma,b]O(registron) para cada um desses intervalos e use a fórmula acima para recalcular u ( x , y ) para cada um desses intervalos e cada um de seus ancestrais. A operação de diminuição é a mesma com um decremento em vez de um incremento.c(x,y)você(x,y)

David Eppstein
fonte
Acho que não entendi sua segunda bala. Na subárvore com rot rotulada , quais células não são cobertas por subconjuntos particionados de intervalos em [ x , y ] ? O intervalo inteiro [ x , y ] não é coberto, então u ( x , y ) = 0 ? [x,y][x,y][x,y]você(x,y)=0 0
Jbapple #
[x,y][x,y][x,y] em sua partição) ele diminui.
David Eppstein
Você poderia dar um exemplo?
Jbapple
Suponha que seu intervalo seja o número [1,8]. É recursivamente dividido em [1,4], [4,8], depois [1,2], [3,4], [5,6] e [7,8], e em seguida todos os intervalos de um elemento. Inicialmente, tudo é descoberto, todos c [x, y] = 0 e cada intervalo possui u = seu comprimento. Mas então, suponha que você execute uma operação de aumento [2,6]. Os intervalos máximos O (log n) nos quais [2,6] podem ser decompostos são [2,2], [3,4] e [5,6], portanto, definimos c [x, y] para esses três varia de 1. De acordo com a fórmula da minha resposta, isso faz com que u [x, y] para esses três intervalos também se tornem 0. u [1,2] se torna 1, u [1,4] também se torna 1, u [ 5,8] = 2, e u [1,8] = 1 + 2 = 3
David Eppstein