Dynamic Range Minimum Queries

#include <vector>
#include <iostream>
#include <climits>  // Para usar INT_MAX como valor inicial de mínimo

using namespace std;

class SegmentTree {
private:
    std::vector<int> tree;
    int n;

    // Función para construir el árbol desde el arreglo original
    void build(const std::vector<int>& data) {
        // Copiamos los datos al final del árbol (las hojas)
        for (int i = 0; i < n; i++) {
            tree[n + i] = data[i];
        }
        // Construimos los nodos internos desde los hijos
        for (int i = n - 1; i > 0; --i) {
            tree[i] = std::min(tree[2 * i], tree[2 * i + 1]);
        }
    }

public:
    // Constructor para inicializar el árbol
    SegmentTree(const std::vector<int>& data) {
        n = data.size();
        tree.resize(2 * n);
        build(data);
    }

    // Función para consultar el mínimo en el rango [l, r]
    int rangeMin(int l, int r) {
        l += n;  // Ajustamos el índice para el nivel de las hojas
        r += n;  // Ajustamos el índice para el nivel de las hojas
        int minVal = INT_MAX;  // Inicializamos el mínimo como el valor más grande posible
        while (l <= r) {
            if (l % 2 == 1) minVal = std::min(minVal, tree[l++]);  // Si l es impar, comparamos y avanzamos
            if (r % 2 == 0) minVal = std::min(minVal, tree[r--]);  // Si r es par, comparamos y retrocedemos
            l /= 2;  // Subimos un nivel
            r /= 2;  // Subimos un nivel
        }
        return minVal;
    }

    // Función para actualizar un valor en una posición específica
    void update(int index, int value) {
        index += n;  // Ajustamos el índice para el nivel de las hojas
        tree[index] = value;  // Actualizamos el valor en la hoja
        for (index /= 2; index > 0; index /= 2) {  // Subimos actualizando los nodos padres
            tree[index] = std::min(tree[2 * index], tree[2 * index + 1]);
        }
    }
};

int main() {
    // Ejemplo de uso
    int n, q;
    cin >> n >> q;

    vector<int> data(n);

    for (int i = 0; i < n; ++i) {
        cin >> data[i];
    }
    SegmentTree segTree(data);

    for (int i = 0; i < q; ++i) {
        int p;
        cin >> p;
        if (p == 1) {
            int k, u;
            cin >> k >> u;
            segTree.update(k - 1, u);  // Convertimos k a base cero
        } 
        else if (p == 2) {
            int a, b;
            cin >> a >> b;
            cout << segTree.rangeMin(a - 1, b - 1)<<endl;  // Convertimos a y b a base cero
        }
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED