Range Minimum Query (RMQ)

/*

Segment Tree

Rodrigo Paes

RMQ - Range Minimum Query com atualização dinâmica.

Caso os valores do array não precisem ser atualizados, utilizar

sparse table.

*/

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

#define pb push_back

vi st; //segment tree

vi a; // list of elements

/*

Constrói a segment tree com base no vector a.

O(n)

*/

void build(int idx=1, int left=1, int right=a.size())

{   

    if (right - left < 2) // se o intervalo tiver 1 elemento, ou zero

    {

        st[idx] = left; // guarda o índice do menor

        return;

    }

    int mid = (left+right)  / 2;

    build(idx * 2, left, mid);

    build(idx * 2+1, mid, right);

    int pos1 = st[idx * 2];

    int pos2 = st[idx * 2 + 1];

    // ao invés de somar, guarda o índice do menor elemento daquele intervalo

    st[idx] = (a[pos1] < a[pos2]) ? pos1 : pos2;

}

/*

Retorna o menor elemento de um intervalo

x = posição inicial do intervalo (intervalo fechado)

y = posição final do intervalo (intervalo aberto)

idx = índice atual da segment tree

left = início do intervalo do nó idx

right = fim do intervalo do nó idx

O(log(n))

*/

int rmq(int x, int y, int idx = 1, int left = 1, int right = a.size())

{   

    if ( x >= right || y <= left)

    {

        /* se o início do intervalo desejado (x) for maior ou igual ao right

        significa que o intervalo está à direita desse nó idx e, portanto,

        fora do intervalo desse nó.

        O mesmo raciocínio se aplica ao fim. Ou seja, se o fim do intervalo

        é menor que o início do intervalo do nó idx significa que o intervalo

        está à esquerda do nó.

        */

        return -1; //fora do intervalo

    }

    if ( x <= left  && y >= right)

    {

        /*

        Nesse caso temos:

            left      right

              |            |

              |                |

              x                y

        O intervalo do nó está contido no intervalo desejado, assim,

        não faz sentido dividir o intervalo em pedaços ainda menores,

        ou seja, não faz sentido continuar descendo na árvore ainda mais

        pois a informação mais agregada já está contida nesse nó

        */

        return st[idx];

    }   

    int mid = (left+right) / 2;   

    int pos1 = rmq(x,y, idx*2, left, mid);

    int pos2 = rmq(x, y, idx*2+1, mid, right);

    if (pos1==-1) return pos2;

    if (pos2==-1) return pos1;

    return (a[pos1] < a[pos2]) ? pos1 : pos2;

}

/*

O(log(n))

*/

void modify(int pos, int value, int idx = 1, int left=1, int right = a.size())

{

    if (right - left < 2)

    {

        a[pos] = value;

        return;

    }

    int mid = (left+right) / 2;   

    // Só precisa alterar um ramo

    if (pos < mid)

    {

        modify(pos, value, idx*2, left, mid);

    }

    else

    {

        modify(pos, value, idx*2+1, mid, right);

    }

    // atualiza a árvore para guardar o menor

    int pos1 = st[idx * 2];

    int pos2 = st[idx * 2 + 1];   

    st[idx] = (a[pos1] < a[pos2]) ? pos1 : pos2;

}

int main()

{

    a.pb(-1); // Ignora a posição 0

    // Elementos do array

    a.pb(10);

    a.pb(2);

    a.pb(30);

    a.pb(4);

    a.pb(15);

    a.pb(6);

    st.resize(a.size() *4); // 4n para o pior caso

    build();

    for (auto it : st)

    {

        cout << it <<" ";

    }

    cout << endl;

    cout << rmq(1,5) << endl; // espera-se rmq(10, 3, 30, 8) = 2

    modify(2,12); // passou de 3 para 12

    cout << rmq(1,5) << endl; // espera-se: rmq(10, 12, 30, 8) = 4

    return 0;

}