Dynamic Range Minimum Queries

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    
    int biggestpower = 1;
    while (biggestpower < n)
        biggestpower *= 2;
    
    vector<int> segmentTree(biggestpower * 2);
    
    for (int i = biggestpower; i < biggestpower + n; i++)
    {
        cin >> segmentTree[i];
    }
    for (int i = biggestpower + n; i < biggestpower * 2; i++)
        segmentTree[i] = INT_MAX;
    
    for (int i = biggestpower - 1; i > 0; i--)
    {
        segmentTree[i] = min(segmentTree[2 * i], segmentTree[2 * i + 1]);
    }
    
    // Process a query
    for (int i = 0; i < q; i++)
    {
        /*
        cout << "Map: ";
        for (int i = 0; i < segmentTree.size(); i++)
            cout << segmentTree[i] << " ";
        cout << endl;
        */
        
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            // Update b to c
            b += biggestpower - 1;
            segmentTree[b] = c;
            b /= 2;
            while (b > 0)
            {
                segmentTree[b] = min(segmentTree[2*b], segmentTree[2*b+1]);
                b /= 2;
            }
        }
        else
        {
            // Print min from b to c
            b += biggestpower - 1;
            c += biggestpower - 1;
            int minVal = INT_MAX;
            while (b <= c)
            {
                // cout << b << " - " << c << " - " << minVal << endl;
                if (b % 2 == 1)
                    minVal = min(minVal, segmentTree[b++]);
                if (c % 2 == 0)
                    minVal = min(minVal, segmentTree[c--]);
                
                b /= 2;
                c /= 2;
            }
            
            cout << minVal << endl;
        }
    }
    

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED