Question - 3

Given an array of N positive integers. The task is to perform the following operations according to the type of query given. 1. Print the maximum pair product in a given range. [L-R] 2. Update Ai with some given value.

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: 12 24

For the query1, the maximum product in a range [0, 2] is 3*4 = 12. For the query2, after an update, the array becomes [1, 6, 4, 2, 5] For the query3, the maximum product in a range [0, 2] is 6*4 = 24.

class Solution {
    static class Pair {
        int max, smax;

        Pair(int max, int smax) {
            this.max = max;
            this.smax = smax;
        }
    }

    public static void buildTree(int[] arr, Pair[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], Integer.MIN_VALUE);
            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] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

    public static Pair findMaxProd(Pair[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(Integer.MIN_VALUE, Integer.MIN_VALUE);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair leftPair = findMaxProd(tree, start, mid, 2 * index, L, R);
        Pair rightPair = findMaxProd(tree, mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(0, 0);
        ans.max = Math.max(leftPair.max, rightPair.max);
        ans.smax = Math.min(Math.max(leftPair.max, rightPair.smax), Math.max(leftPair.smax, rightPair.max));
        return ans;
    }

    public static void updateElement(int[] arr, Pair[] tree, int start, int end, int index, int updateIndex,
            int value) {
        if (start == end) {
            arr[start] = value;
            tree[index] = new Pair(value, Integer.MIN_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] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

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