Dynamic Range Minimum Queries

#include <bits/stdc++.h>

using namespace std;

int segtree_create_rec(int input[], int segment_start, int segment_end, int *output, int index) {

    if (segment_start == segment_end) {
        output[index] = input[segment_start];
        return output[index];
    } else {
        int mid = (segment_start + segment_end) / 2;
        output[index] = min(
            segtree_create_rec(input, segment_start, mid, output, 2*index+1),
            segtree_create_rec(input, mid+1, segment_end, output, 2*index+2)
        );
        return output[index];
    }

}

int *segtree_create(int input[], int n) {

    int x = (int) ceil(log2(n));
    int max_size = 2 * (int) pow(2, x) - 1;
    int *output = new int[max_size];
    segtree_create_rec(input, 0, n-1, output, 0);
    return output;

}

int segtree_min_rec(int *segtree, int segment_start, int segment_end, int query_start, int query_end, int index) {
    if (query_start <= segment_start && query_end >= segment_end)
        return segtree[index];
    if (segment_end < query_start || segment_start > query_end)
        return INT_MAX;
    int mid = (segment_start + segment_end) / 2;
    return min(
        segtree_min_rec(segtree, segment_start, mid, query_start, query_end, 2*index+1),
        segtree_min_rec(segtree, mid+1, segment_end, query_start, query_end, 2*index+2)
    );
}

int segtree_min(int *segtree, int n, int query_start, int query_end) {
    // (query_start >= 0 && query_end <= n-1 && query_start <= query_end)
    return segtree_min_rec(segtree, 0, n-1, query_start, query_end, 0);
}

void segtree_update_rec(int *segtree, int index, int segment_start, int segment_end, int at, int new_value) {
    int mid = segment_start + (segment_end - segment_start) / 2;
    if (segment_start == segment_end && segment_start == at) {
        segtree[index] = new_value;
    } else if (mid >= at) {
        segtree_update_rec(segtree, 2*index+1, segment_start, mid, at, new_value);
        segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);
    } else {
        segtree_update_rec(segtree, 2*index+2, mid+1, segment_end, at, new_value);
        segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);
    }
}

void segtree_update(int *segtree, int n, int at, int new_value) {
    segtree_update_rec(segtree, 0, 0, n-1, at, new_value);
}

int main() {

    int n, q;
    cin >> n >> q;

    int *x = new int[n];
    
    for (int i = 0; i < n; i++)
        cin >> x[i];
    
    struct query_t {
        int x, y, z;
    };
    
    query_t *queries = new query_t[q];

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        queries[i] = {x, y, z};
    }

    int *segtree = segtree_create(x, n);

    vector<int> output;

    for (int i = 0; i < q; i++) {
        auto query = queries[i];

        if (query.x == 1) {
            segtree_update(segtree, n, query.y-1, query.z);
            x[query.y-1] = query.z;
        } else {
            int m = segtree_min(segtree, n, query.y-1, query.z-1);
            output.push_back(m);
        }
    }

    for (int o : output)
        cout << o << endl;

    return 0;
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED