Question - 2

Given an array A of size N, there are two types of queries on this array.

1) l r: In this query you need to print the minimum in the sub-array A[l:r].

2) x y: In this query you need to update A[x]=y.

Examples:

Input: A={1, 3, 4, 2, 5} Queries: Type 1: L = 0, R = 2. Type 2: i = 1, val = 6 Type 1: L = 0, R = 2.

Output: 1 1

class Solution {
    public static void buildTree(int[] arr, int[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = Math.min(tree[2 * index], tree[2 * index + 1]);
    }

    public static int findMin(int[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return Integer.MAX_VALUE;
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        int leftMin = findMin(tree, start, mid, 2 * index, L, R);
        int rightMin = findMin(tree, mid + 1, end, 2 * index + 1, L, R);
        return Math.min(leftMin, rightMin);
    }

    public static void updateElement(int[] arr, int[] tree, int start, int end, int index, int updateIndex, int value) {
        if (start == end) {
            arr[start] = value;
            tree[index] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        if (updateIndex > mid)
            updateElement(arr, tree, mid + 1, end, 2 * index + 1, updateIndex, value);
        else
            updateElement(arr, tree, start, mid, 2 * index, updateIndex, value);
        tree[index] = Math.min(tree[2 * index], tree[2 * index + 1]);
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int tree[] = new int[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            if (query[0] == 1)
                System.out.println(findMin(tree, 0, n - 1, 1, query[1], query[2]));
            else
                updateElement(arr, tree, 0, n - 1, 1, query[1], query[2]);
        }
    }
}