Recuperando o valor máximo de um intervalo em uma matriz não classificada

Eu tenho uma matriz não classificada . Tenho consultas nas quais dou um intervalo e, em seguida, o valor máximo desse intervalo deve ser retornado. Por exemplo:

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

Qual algoritmo ou estrutura de dados eu construo para recuperar rapidamente o valor máximo de qualquer intervalo. (Existem muitas consultas)

Edição: Esta é realmente uma versão simples do problema real. Posso ter um tamanho de matriz tão grande quanto 100000 e o número de consultas até 100000. Portanto, eu definitivamente preciso de algum pré-processamento que facilitará uma resposta rápida à consulta.

Eu acho que você poderia construir algum tipo de árvore binária em que cada nó representa o valor máximo de seus filhos:

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Então, você só precisa encontrar uma maneira de determinar quais nós você precisa verificar minimamente para encontrar o valor máximo no intervalo consultado. Neste exemplo, para obter o valor máximo no intervalo de índice [2, 6](inclusive), você teria em max(45, 78, 4)vez de max(9, 45, 78, 2, 4). À medida que a árvore cresce, o ganho será maior.

Para complementar a resposta de ngoaho91.

A melhor maneira de resolver esse problema é usar a estrutura de dados da Árvore de Segmentos. Isso permite que você responda a essas consultas em O (log (n)), o que significaria que a complexidade total do seu algoritmo seria O (Q logn), em que Q é o número de consultas. Se você usasse o algoritmo ingênuo, a complexidade total seria O (Q n), que é obviamente mais lenta.

Há, no entanto, uma desvantagem no uso de árvores de segmentos. É preciso muita memória, mas muitas vezes você se importa menos com a memória do que com a velocidade.

Descreverei brevemente os algoritmos usados ​​por este DS:

A árvore de segmentos é apenas um caso especial de uma Árvore de Pesquisa Binária, em que cada nó contém o valor do intervalo ao qual está atribuído. O nó raiz é atribuído ao intervalo [0, n]. O filho esquerdo recebe o intervalo [0, (0 + n) / 2] e o filho direito [(0 + n) / 2 + 1, n]. Desta forma, a árvore será construída.

Criar árvore :

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Árvore de consulta

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

Se você precisar de mais explicações, entre em contato.

BTW, a Árvore de segmentos também suporta a atualização de um único elemento ou de um intervalo de elementos em O (log n)

O melhor algoritmo seria em O (n) tempo, como abaixo, deixe começar, final seja o índice dos limites do intervalo

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}

As soluções baseadas em árvore binária / segmento de árvore estão de fato apontando na direção certa. Pode-se objetar que eles exigem muita memória extra, no entanto. Existem duas soluções para esses problemas:

1. Use uma estrutura de dados implícita em vez de uma árvore binária
2. Use uma árvore M-ária em vez de uma árvore binária

O primeiro ponto é que, como a árvore é altamente estruturada, você pode usar uma estrutura semelhante a heap para definir implicitamente a árvore, em vez de representá-la com nós, ponteiros esquerdo e direito, intervalos, etc. Isso economiza muita memória com essencialmente sem desempenho atingido - você precisa executar um pouco mais de aritmética de ponteiro.

O segundo ponto é que, ao custo de um pouco mais de trabalho durante a avaliação, você pode usar uma árvore M-ária em vez de uma árvore binária. Por exemplo, se você usar uma árvore de 3 árias, calculará o máximo de 3 elementos por vez, 9 elementos por vez e 27, etc. O armazenamento extra necessário será N / (M-1) - você pode provar usando a fórmula da série geométrica. Se você escolher M = 11, por exemplo, precisará de 1/10 do armazenamento do método da árvore binária.

Você pode verificar se essas implementações ingênuas e otimizadas no Python fornecem os mesmos resultados:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

vs.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level 

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)

tente a estrutura de dados da "árvore de segmentos",
existem 2 etapas
build_tree () O (n)
consulta (int min, int max) O (nlogn)

http://en.wikipedia.org/wiki/Segment_tree

editar:

vocês simplesmente não leem o wiki que eu enviei!

esse algoritmo é:
- você percorre o array 1 vez para construir a árvore. O (n)
- próximas 100000000+ vezes que você deseja conhecer o máximo de qualquer parte da matriz, basta chamar a função de consulta. O (logn) para cada consulta
- o c ++ implementa aqui o
algoritmo antigo geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ :
cada consulta, basta percorrer a área selecionada e encontrar.

então, se você usar esse algoritmo para processar uma vez, OK, é mais lento que o antigo. mas se você vai processar grande número de consulta (bilhões), é muito eficiente você pode gerar arquivo de texto como este, para o teste de

linha 1: 50000 número aleatório 0-1.000.000, dividido por '(espaço)' (é o array)
linha Número aleatório 2: 2 de 1 a 50000, dividido por '(espaço)' (é a consulta)
...
linha 200000: gosta da linha 2, também é consulta aleatória

este é o exemplo do problema, desculpe, mas isso está no vietnamita
http://vn.spoj.com/problems/NKLINEUP/
se você o resolver da maneira antiga, nunca será aprovado.

Você pode obter O (1) por consulta (com construção O (n log n)) usando a estrutura de dados chamada tabela esparsa. Para cada potência de 2, vamos salvar o máximo para cada segmento desse comprimento. Agora, dado o segmento [l, r), você obtém o máximo de máximos em [l + 2 ^ k) e [r-2 ^ k, r) para o k apropriado. Eles se sobrepõem, mas tudo bem