Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <climits>

// Clase para manejar sumas de segmentos
class SumSegmentTree {
private:
    std::vector<int> tree;
    std::vector<int> data;
    int n;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r);
    }

    void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            data[idx] = value;
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                update(2 * node + 1, start, mid, idx, value);
            } else {
                update(2 * node + 2, mid + 1, end, idx, value);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

public:
    SumSegmentTree(const std::vector<int>& initial_data) : data(initial_data) {
        n = initial_data.size();
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }

    int sum(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    void update(int idx, int value) {
        update(0, 0, n - 1, idx, value);
    }
};

// Clase para manejar mínimos de segmentos
class MinSegmentTree {
private:
    std::vector<int> tree;
    std::vector<int> data;
    int n;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return INT_MAX;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        return std::min(query(2 * node + 1, start, mid, l, r), query(2 * node + 2, mid + 1, end, l, r));
    }

    void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            data[idx] = value;
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                update(2 * node + 1, start, mid, idx, value);
            } else {
                update(2 * node + 2, mid + 1, end, idx, value);
            }
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    MinSegmentTree(const std::vector<int>& initial_data) : data(initial_data) {
        n = initial_data.size();
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }

    int minimum(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    void update(int idx, int value) {
        update(0, 0, n - 1, idx, value);
    }
};

// Clase para manejar máximos de segmentos
class MaxSegmentTree {
private:
    std::vector<int> tree;
    std::vector<int> data;
    int n;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = data[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) {
            return INT_MIN;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        return std::max(query(2 * node + 1, start, mid, l, r), query(2 * node + 2, mid + 1, end, l, r));
    }

    void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            data[idx] = value;
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                update(2 * node + 1, start, mid, idx, value);
            } else {
                update(2 * node + 2, mid + 1, end, idx, value);
            }
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    MaxSegmentTree(const std::vector<int>& initial_data) : data(initial_data) {
        n = initial_data.size();
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }

    int maximum(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }

    void update(int idx, int value) {
        update(0, 0, n - 1, idx, value);
    }
};

using namespace std;
int main() {

    int n, q;
    cin >> n >> q;
    
    vector <int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    MinSegmentTree t(arr);

    
    for (int i = 0; i < q; i++)
    {
        int command;
        cin >> command;
        if (command == 1) {
            int k, u;
            cin >> k >> u;
            t.update(k - 1, u);
        }

        else {
            int a, b;
            cin >> a >> b;
            cout << t.minimum(a - 1, b - 1) << endl;
        }
    }
  
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED