Dynamic Range Minimum Queries

#include <iostream>
#include <vector>
#include <climits>
using namespace std;


class SegmentTreeSum {
    vector<int> tree;
    int n;

public:
    SegmentTreeSum(const vector<int>& array) {
        n = array.size();
        tree.resize(2 * n);
        build(array);
    }

    void build(const vector<int>& array) {
        for (int i = 0; i < n; i++) 
            tree[n + i] = array[i];
        for (int i = n - 1; i > 0; --i)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    int rangeSum(int l, int r) {
        int sum = 0;
        l += n; r += n;
        while (l < r) {
            if (l & 1) sum += tree[l++];
            if (r & 1) sum += tree[--r];
            l >>= 1; r >>= 1;
        }
        return sum;
    }

    void update(int idx, int value) {
        idx += n;
        tree[idx] = value;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
        }
    }
};


class SegmentTreeMin {
    vector<int> tree;
    int n;

public:
    SegmentTreeMin(const vector<int>& array) {
        n = array.size();
        tree.resize(2 * n);
        build(array);
    }

    void build(const vector<int>& array) {
        for (int i = 0; i < n; i++)
            tree[n + i] = array[i];
        for (int i = n - 1; i > 0; --i)
            tree[i] = min(tree[2 * i], tree[2 * i + 1]);
    }

    int rangeMin(int l, int r) {
        int minVal = INT_MAX;
        l += n; r += n;
        while (l < r) {
            if (l & 1) minVal = min(minVal, tree[l++]);
            if (r & 1) minVal = min(minVal, tree[--r]);
            l >>= 1; r >>= 1;
        }
        return minVal;
    }

    void update(int idx, int value) {
        idx += n;
        tree[idx] = value;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = min(tree[2 * idx], tree[2 * idx + 1]);
        }
    }
};


class SegmentTreeMax {
    vector<int> tree;
    int n;

public:
    SegmentTreeMax(const vector<int>& array) {
        n = array.size();
        tree.resize(2 * n);
        build(array);
    }

    void build(const vector<int>& array) {
        for (int i = 0; i < n; i++)
            tree[n + i] = array[i];
        for (int i = n - 1; i > 0; --i)
            tree[i] = max(tree[2 * i], tree[2 * i + 1]);
    }

    int rangeMax(int l, int r) {
        int maxVal = INT_MIN;
        l += n; r += n;
        while (l < r) {
            if (l & 1) maxVal = max(maxVal, tree[l++]);
            if (r & 1) maxVal = max(maxVal, tree[--r]);
            l >>= 1; r >>= 1;
        }
        return maxVal;
    }

    void update(int idx, int value) {
        idx += n;
        tree[idx] = value;
        for (idx >>= 1; idx > 0; idx >>= 1) {
            tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
        }
    }
};


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

    vector<int> v(n);

    for(int i=0; i<n; i++) cin>>v[i];

    SegmentTreeMin STs(v);

    for(int i=0; i<q; i++){
        int type,a,b;
        cin >> type >> a >> b;
        if(type==1){
            STs.update(a-1,b);
        }
        else cout << STs.rangeMin(a-1,b) << endl;
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED