Dynamic Range Minimum Queries

Note: input/Queries.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.

import java.io.IOException;
import java.io.StreamTokenizer;
import java.io.BufferedInputStream;

class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int[] arr) {
        this.n = this.nextPow2(arr.length);
        this.tree = new int[2 * this.n];
        int ix = 2 * this.n - 1;

        for (int i = 0; i < n - arr.length; i++)
            this.tree[ix--] = Integer.MAX_VALUE;

        for (int i = arr.length - 1; i >= 0; i--)
            this.tree[ix--] = arr[i];

        while (ix >= 1) {
            this.tree[ix] = Math.min(this.tree[2 * ix], this.tree[2 * ix + 1]);
            ix--;
        }
    }

    private int nextPow2(int n) {
        if (n <= 1)
            return 1;
        return 1 << (32 - Integer.numberOfLeadingZeros(n - 1));
    }

    public void update(int k, int u) {
        k = this.n + k - 1;
        this.tree[k] = u;
        k = Math.floorDiv(k, 2);
        while (k >= 1) {
            this.tree[k] = Math.min(this.tree[2 * k], this.tree[2 * k + 1]);
            k = Math.floorDiv(k, 2);
        }
    }

    public int min(int a, int b, int node, int l, int r) {
        if (l > b && r < a)
            return Integer.MAX_VALUE;

        if (node > this.tree.length)
            return Integer.MAX_VALUE;

        if (a <= l && b >= r)
            return this.tree[node];

        int mid = Math.floorDiv(l + r, 2);
        return Math.min(this.min(a, b, node * 2 + 1, mid + 1, r), this.min(a, b, node * 2, l, mid));

    }

}

public class Queries {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));

        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int q = (int) in.nval;

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
        }

        SegmentTree st = new SegmentTree(arr);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            in.nextToken();
            int op = (int) in.nval;
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;

            if (op == 1) {
                st.update(x, y);
            } else {
                sb.append(st.min(x, y, 1, 1, st.n)).append('\n');
            }
        }

        System.out.print(sb);
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED