You are given an array of n numbers a [0..n-1]. The numbers are not sorted and their ordering is fixed. You have an application in which you need to determine the minimum value in various sub-arrays of a [] (and you may issue many such queries). In other words, you need to support a query MIN ELEM (low, hi) which yields the smallest value in the subarray from index low to index hi. You might make many such queries. As an example, in the array below, MIN ELEM (1,4)=2.9 ; MIN ELEM (5,5)=11.4 ; MIN_ELEM (3,9) =1.12; MIN_ELEM (1,5) =2.9) idx i 0 1 2 3 4 5 6 7 8 9 a[i] 4.1 2.9 6.6 9. 1 7 .1 11.4 1.12 3.13 1.9 8.1 Since you are going to do lots of queries, you are willing to do some preprocessing work beforehand to make the queries faster. A matrix-based approach: Preprocess: build an nxn matrix M where M[low, hi] stores the minimum value in subarray a [low ... hi]. (Matrix entries MIN[i,j] where > i>j are ignored). Queries: Now queries are trivial and take O(1) time just by accessing the correct matrix entry. TODO-A (25 pts): Devise an algorithm to build this matrix in Oln) time (a trivial brute-force approach takes O(ni") time). O(1) query time is nice, but quadratic time for the preprocess might be pretty lousy unless | am going to do a lot of queries (like 2(na) queries). Maybe we prefer a slightly slower query time if we can shrink the preprocessing time a lot? In particular, here is your goal: TODO-B' (35 pts): You will still have a preprocess to build a data structure but it won't be a matrix (you will design the data structure) but you will limit yourself to O(n) time for this step. Subsequent queries are done in O(log n) time. Your Job: Design a data structure, construction procedure and query procedure meeting these goals. Explain why the runtime requirements are met