Dynamic Range Minimum Queries

import java.io.*;
import java.util.*;

public class Dynamic {


    static int[] tree;
    static int n;

    static void build(int[] arr, int node, int left, int right) {
        if (left == right) {
            tree[node] = arr[left];
            return;
        }
        int mid = (left + right) / 2;
        build(arr, node * 2, left, mid);
        build(arr, node * 2 + 1, mid + 1, right);

        tree[node] = Math.min(tree[node * 2], tree[node * 2 + 1]);
    }
    static void update(int node, int left, int right, int pos, int value) {
        if (left == right) {
            tree[node] = value;
            return;
        }

        int mid = (left + right) / 2;

        if (pos <= mid) {
            update(node * 2, left, mid, pos, value);
        } else {
            update(node * 2 + 1, mid + 1, right, pos, value);
        }

        tree[node] = Math.min(tree[node * 2], tree[node * 2 + 1]);
    }
    static int query(int node, int left, int right,
                     int queryLeft, int queryRight) {
        if (right < queryLeft || queryRight < left) {
            return Integer.MAX_VALUE;
        }

        if (queryLeft <= left && right <= queryRight) {
            return tree[node];
        }
        int mid = (left + right) / 2;
        int minLeft = query(node * 2, left, mid, queryLeft, queryRight);
        int minRight = query(node * 2 + 1, mid + 1, right, queryLeft, queryRight);

        return Math.min(minLeft, minRight);
    }

    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        int q = scanner.nextInt();

        int[] arr = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            arr[i] = scanner.nextInt();
        }
        tree = new int[4 * n];

        build(arr, 1, 1, n);

        StringBuilder output = new StringBuilder();

        while (q-- > 0) {
            int type = scanner.nextInt();
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            if (type == 1) {
                update(1, 1, n, a, b);
            } else {
                int answer = query(1, 1, n, a, b);
                output.append(answer).append('\n');
            }
        }
        System.out.print(output);
    }

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED