Procure o valor máximo menor que V em uma matriz composta por K funções lineares

Question

Desculpe pela falta de clareza na descrição da pergunta.

Eu tenho uma matriz composta por comprimento $N$ composto de $K$ submatrizes lineares.Definimos uma submatriz linear como uma submatriz contígua da matriz $[eu,r]$ onde $A[i]-A[i-1] = C$, uma constante, para todos $l<i<=r$.(Observação: $C$ pode ser diferente para diferentes submatrizes;os elementos da matriz são inteiros.) Observe que as submatrizes lineares não são disjuntos (há uma interseção de elemento entre qualquer par de submatrizes lineares adjacentes).Por exemplo, [1,3,5,4,3,2] tem duas submatrizes lineares:[1,3,5] e [5,4,3,2].[1,3,5,1,2,3] teria três:[1,3,5], [5,1], [1,2,3].

Desejo encontrar várias consultas para o valor máximo menor que um valor consultado $V$, em $o(K)$ e $o(N)$ tempo por consulta, com $o(K^2)$ e $o(N)$ pré-processando.(Suponha que o array já tenha sido armazenado em termos do K submatrizes lineares, talvez em termos da constante C e comprimento de cada submatriz, com as submatrizes ordenadas.Portanto, você recebe a matriz com os pontos inicial e final de todas as submatrizes lineares, bem como a constante linear C, conforme descrito anteriormente.Portanto, em primeiro lugar, não é necessário derivar as submatrizes lineares.) Caso contrário, seria apreciada uma prova (formal ou não) de que não é possível fazê-lo.

É claro que uma árvore de busca binária balanceada (BBST) ou simplesmente uma classificação atingem o objetivo, mas requer $O(NlogN)$ pré-processamento, o que é demais.Verificar o maior valor válido dentro de cada submatriz leva $O(K)$ por consulta, o que novamente é demais.Seria possível que algo combinasse ambos, talvez?

Algoritmos randomizados são aceitáveis, desde que sempre obtenham a resposta correta e funcionem com rapidez suficiente no caso médio, embora algoritmos determinísticos sejam preferidos.

Obrigado por toda e qualquer resposta.Eu queria saber se houve alguma pesquisa sobre a questão, talvez?Não parece um tema muito obscuro, mas infelizmente a minha pesquisa não foi suficientemente competente.

EDITAR:Um método que parece útil.

Esta foi minha linha de pensamento depois de fazer a pergunta;Eu me pergunto se isso ajudaria de alguma forma.Ele também usa a ideia de módulo.Inicializar V=0, e permitir que cada submatriz linear seja armazenada como L,R;onde L é o valor mínimo do subarray e R é o valor máximo.Quando nos é dada uma consulta para V, de alguma forma desincluímos elementos onde L>V e R<V (talvez usando múltiplas dimensões?) Uma estrutura de dados suplementar armazena a diferença teórica mínima do elemento na matriz, que é algo como L - V mod c[i].Então, essencialmente, agora precisamos ser capazes de executar uma adição de intervalo nesta estrutura de dados, mas se o valor de qualquer elemento se tornar <0 ou >=c[i] ele precisa ser redefinido (por exemplo.se um elemento se tornar igual a -1 com c[i]=5 ele será redefinido para 4;se um elemento se tornasse igual a 6 com o mesmo c[i] seria redefinido para 1);e também execute consultas de intervalo mínimo.

Se tal estrutura de dados puder ser feita, o problema estará resolvido.O problema é o módulo, já que a adição de intervalo e a consulta mínima de intervalo podem ser feitas facilmente com uma árvore de segmentos e propagação lenta;bem como a desinclusão de determinados elementos.

Answer 1

Não é possível garantir encontrar o valor máximo menor que um valor consultado $V$ em $o(K)$ tempo com pré-processamento em $o(N)$ tempo.

Isto pode ser visto facilmente no seguinte caso extremo.Deixar $A$ ser qualquer matriz de $N$ inteiros, que é composto pelos seguintes $K=N-1$ submatrizes lineares.

• a submatriz $A[0], A[1]$ com $C=A[1]-A[0]$.
• a submatriz $A[1], A[2]$ com $C=A[2]-A[1]$.
• $\cdots$
• a submatriz $A[N-2], A[N-1]$ com $C=A[N-1]-A[N-2]$.

Com $o(N)$ pré-processamento de tempo e $o(K)=o(N)$ processamento de tempo, um algoritmo não será capaz de ler algum número em $A$ quando $N$ é grande o suficiente.(Na verdade, a maioria dos números em $A$.) Então, para algum valor consultado $q$, o algoritmo não conseguirá reconhecer que $q+1$ aparece em $A$.

(A explicação acima poderia ser mais rigorosa, por exemplo, usando o método formal do adversário e um modelo de computação bem definido.)

---

Parece que a pergunta mais interessante a ser feita seria se existe um algoritmo com $o(N\log N)$ pré-processamento e $o(K)$ por consulta.Ou se existe um algoritmo com $o(N)$ pré-processamento e $o(K)$ por consulta dada $K=o(N)$.Isso soa como outra pergunta, de qualquer maneira.