Conceitos Fundamentais do FHQ-Treap

O FHQ-Treap opera através das operações de divisão e mesclagem, permitindo manutanção de sequências e persistência. Armazena dados como filhos esquerdo (esq) e direito (dir), valor (chave), tamanho da subárvore (tam) e valor aleatório (prior) para balanceamento.

Autalização de Tamanho

void atualizar_tamanho(int no) {
    arvore[no].tam = arvore[arvore[no].esq].tam + arvore[arvore[no].dir].tam + 1;
}

Criação de Nó

int novo_no(int valor) {
    arvore[++contador] = {0, 0, valor, rand(), 1};
    return contador;
}

Divisão por Valor

void dividir_valor(int no, int valor_ref, int &esq, int &dir) {
    if (!no) { esq = dir = 0; return; }
    if (arvore[no].chave <= valor_ref) {
        esq = no;
        dividir_valor(arvore[no].dir, valor_ref, arvore[no].dir, dir);
    } else {
        dir = no;
        dividir_valor(arvore[no].esq, valor_ref, esq, arvore[no].esq);
    }
    atualizar_tamanho(no);
}

Divisão por Tamanho

void dividir_tamanho(int no, int tam_ref, int &esq, int &dir) {
    if (!no) { esq = dir = 0; return; }
    int tam_esq = arvore[arvore[no].esq].tam;
    if (tam_esq < tam_ref) {
        esq = no;
        dividir_tamanho(arvore[no].dir, tam_ref - tam_esq - 1, arvore[no].dir, dir);
    } else {
        dir = no;
        dividir_tamanho(arvore[no].esq, tam_ref, esq, arvore[no].esq);
    }
    atualizar_tamanho(no);
}

Mesclagem

int mesclar(int esq, int dir) {
    if (!esq || !dir) return esq | dir;
    if (arvore[esq].prior < arvore[dir].prior) {
        arvore[esq].dir = mesclar(arvore[esq].dir, dir);
        atualizar_tamanho(esq);
        return esq;
    } else {
        arvore[dir].esq = mesclar(esq, arvore[dir].esq);
        atualizar_tamanho(dir);
        return dir;
    }
}

Inserção

void inserir(int valor) {
    int esq, dir;
    dividir_valor(raiz, valor, esq, dir);
    raiz = mesclar(mesclar(esq, novo_no(valor)), dir);
}

Remoção

void remover(int valor) {
    int esq, meio, dir;
    dividir_valor(raiz, valor, esq, dir);
    dividir_valor(esq, valor - 1, esq, meio);
    meio = mesclar(arvore[meio].esq, arvore[meio].dir);
    raiz = mesclar(mesclar(esq, meio), dir);
}

Cnosulta de Posição

int consultar_posicao(int valor) {
    int esq, dir;
    dividir_valor(raiz, valor - 1, esq, dir);
    int posicao = arvore[esq].tam + 1;
    raiz = mesclar(esq, dir);
    return posicao;
}

Consulta por Posição

int consultar_valor(int no, int pos) {
    int tam_esq = arvore[arvore[no].esq].tam;
    if (pos <= tam_esq) return consultar_valor(arvore[no].esq, pos);
    if (pos == tam_esq + 1) return arvore[no].chave;
    return consultar_valor(arvore[no].dir, pos - tam_esq - 1);
}

Antecessor

int antecessor(int valor) {
    int esq, dir;
    dividir_valor(raiz, valor - 1, esq, dir);
    int resultado = consultar_valor(esq, arvore[esq].tam);
    raiz = mesclar(esq, dir);
    return resultado;
}

Sucessor

int sucessor(int valor) {
    int esq, dir;
    dividir_valor(raiz, valor, esq, dir);
    int resultado = consultar_valor(dir, 1);
    raiz = mesclar(esq, dir);
    return resultado;
}

Inversão de Intervalo

Para inversão de intervalos, utiliza-se divisão por tamanho e marcação de inversão:

void inverter_filhos(int no) {
    if (!no) return;
    std::swap(arvore[no].esq, arvore[no].dir);
    arvore[arvore[no].esq].marca ^= 1;
    arvore[arvore[no].dir].marca ^= 1;
    arvore[no].marca = 0;
}

void inverter_intervalo(int inicio, int fim) {
    int esq, meio, dir;
    dividir_tamanho(raiz, fim, esq, dir);
    dividir_tamanho(esq, inicio - 1, esq, meio);
    arvore[meio].marca ^= 1;
    raiz = mesclar(mesclar(esq, meio), dir);
}