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 {
        FastScanner scanner = new FastScanner(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);
    }

    static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
    	 return Double.parseDouble(next());
	 }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }
}

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED