3. Let A = [a1,a2, . . . an] be an integer array consisting of n integers (80 Points) (a) Design an algorithm that constructs a Binary Tree T such that the leaves of T from left to right are ai,a2,... , an. L.e, left most leaf of T is a1, second from left is a2, and so on, and the rightmost leaf is an. Derive the asymptotic run time of your algorithm in terms of n. (b) Design a data structure that supports the following operations in O(log n) time. increment (i, val): Updates the value of ai to ai val . ss (1): Returns stai Describe the data structure, algorithms to perform above operations, and the derive the time bounds