Dynamic Range Minimum Queries

#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

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

void update(int k, int x, vector<int> &tree, int n) {
    k += n;
    // cout << "updating position " << k << " to " << x << "\n";
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = min(tree[2*k], tree[2*k+1]);
    }
}

int bit_ceil(int n) {
    int res = 1;
    while (res < n) res <<= 1;
    return res;
}

vector<int> create_segment_tree(int n, vector<int> &input, int size) {
    // cout << "size: " << size << "\n";
    vector<int> tree(2 * size, INT_MAX);
    // Add input to the end
    for (int i = 0; i < n; i++) {
        tree[size + i] = input[i];
    }

    // start from the end, from the second last element -> -2
    for (int i = size * 2 - 2; i > 0; i -= 2) {
        tree[i/2] = min(tree[i], tree[i + 1]);
    }

    return tree;
}

int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, q;
	cin >> n >> q;


	// Read values from one line
	vector<int> input_line(n);
	for (int i = 0; i < n; i++) {
		cin >> input_line[i];
	}

    int size = bit_ceil(n);
    vector<int> segment_tree = create_segment_tree(n, input_line, size);

	for (int i = 0; i < q; i++) {
        int type, first, second;
        cin >> type >> first >> second;
        // I use zero based indexing, second must be reduced only when querying
        first--;
        if (type == 1) {
            // cout << "update " << first << " " << second << "\n";
            update(first, second, segment_tree, size);
        } else if (type == 2) {
            second--;
            // cout << "find " << first << " " << second << "\n";
            cout << get_min(first, second, segment_tree, size) << "\n";
        }
	}
    // for (int i = 0; i < 2 * size; i++) {
    //     cout << segment_tree[i] << " ";
    // }
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED