Dynamic Range Minimum Queries

input/code.cpp: In function 'int main()':
input/code.cpp:39:13: warning: unused variable 'val' [-Wunused-variable]
   39 |         int val;
      |             ^~~

#include <iostream>
#include <vector>

using namespace std;

int minimum(vector<int> &v, int n, int a, int b) {
    a += n;
    b += n;
    int min_val = v[a];
    while (a <= b) {
        if (a % 2 == 1) min_val = min(min_val, v[a++]);
        if (b % 2 == 0) min_val = min(min_val, v[b--]);
        a /= 2;
        b /= 2;
    }
    return min_val;
}

void update(vector<int> &v, int n, int k, int u) {
    // Update the values
    k += n;
    v[k] = u;
    
    // Update the minimums
    for (int parent = k/2; parent >= 1; parent /= 2) {
        int child1 = 2 * parent;
        int child2 = 2 * parent + 1;
        v[parent] = min(v[child1], v[child2]);
    }
}

int main() {
    int n, q;
    cin >> n >> q;

    // Read the array
    vector<int> v(2*n);
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> v[n + i];
    }

    // Build the segment tree
    for (int i = n - 1; i >= 1; --i) {
        int child1 = 2 * i;
        int child2 = 2 * i + 1;
        v[i] = min(v[child1], v[child2]);
    }

    // Process the q queries
    for (int i = 0; i < q; ++i)
    {
        int t_query;
        cin >> t_query;

        if (t_query == 1)
        {
            int k, u;
            cin >> k >> u;
            update(v, n, k - 1, u);
        }
        else if (t_query == 2)
        {
            int a, b;
            cin >> a >> b;
            cout << minimum(v, n, a - 1, b - 1) << endl;
        }
        else
        {
            cerr << "Invalid query type: " << t_query << endl;
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED