QuadTree

QuadTree é uma estrutura de dados utilizada para armazenar dados espaciais, e tem como grande vantagem a compressão de dados (que especificamente iremos explorar aqui). Parece um pouco com a árvore binária, mas ao invés de cada nó ter dois filhos, tem quatro, como o nome sugere, e, enquanto a árvore binária pode mapear uma reta, a QuadTree pode ser usada para mapear um espaço 2D.

Funciona assim: suponha que você tem uma imagem no formato .pnm, que nada mais é do que é uma matriz de lado N com bits 1 ou 0, digamos N = 8.

Se a matriz está totalmente preenchida com 1s, não vale a pena armazenar 8x8 = 64 valores, basta um. Mas se temos uma matriz da forma:

Podemos otimizar também o armazenamento, fazendo um nó que subdivide a árvore em 4 árvores iguais.

O nó armazena a informação das 4 submatrizes. Agora, a submatriz SE é a situação inicial da matriz em que todos os elementos são 1s. Recursivamente, definimos o mesmo para cada uma das sub-árvores NW, NE, SW, SE.

Completar a sub-árvore preta fica como missão

Completando com a árvore preta, reduzimos o espaço para 21 nós, o que é bastante satisfatório. Por outro lado, se a matriz fosse um tabuleiro de xadrez, teríamos que utilizar todos os 64 nós como terminais (coloridos) + os nós que apontam para eles, totalizando 85 nós (desvantajoso).

Maior árvore possível

Podemos montar a árvore com a seguinte estrutura de dados:

struct QuadTree {
    QuadTree *ne, *nw, *se, *sw; //As 4 sub-arvores
    bool last; //Se eh ultimo no
    char p; //A informacao que estamos armazenando
};

QuadTree data[MAXN];
int cont_data;
char matriz_original[600][600];

QuadTree *new_node() {
    data[cont_data].last = false;
    data[cont_data].ne = data[cont_data].nw = NULL
    data[cont_data].se = data[cont_data].sw = NULL;
    return &data[cont_data++];
}

QuadTree * mount_tree(QuadTree * node, int px, int py, int side) {
    //Se o lado for de tamanho 1, chegamos em nós terminais
    if(side == 1) {
        node->last = true;
        node->p = matriz_original[px][py];
    }
    //Se nao, resolvemos recursivamente para as sub-arvores
    else {
        node->nw = mount_tree(new_node(), px, py, side/2);
        node->ne = mount_tree(new_node(), px+side/2, py, side/2);
        node->sw = mount_tree(new_node(), px, py+side/2, side/2);
        node->se = mount_tree(new_node(), px+side/2,
                    py+side/2, side/2);
 
        //Se os 4 filhos sao iguais e terminais,
        //entao podemos resumir em um so
        if(node->ne->last && node->se->last
            && node->nw->last && node->sw->last) {
            if(node->ne->p == node->se->p && node->se->p == node->nw->p
                && node->nw->p == node->sw->p) {
                node->last = true;

                //Valor armazenado recebe valor de um dos filhos
                //já que todos os nos de filhos sao iguais
                node->p = node->ne->p;
            }
        }
    }
    return node;
}

A função Mount_tree monta a árvore recursivamente e retorna a raiz. A matriz matriz_original armazena o dado original que queremos consultar. Você pode usar esta estrutura para resolver este problema disponível no URI, basta iterar sobre a árvore já montada.

https://www.urionlinejudge.com.br/judge/pt/problems/view/1725

Sugiro também este problema do UVa:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233

Outros problemas sobre QuadTree:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3092
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3099