Recall the Union-Find data structure presented in class that uses tree linking and path compression to achieve O(1) worst case time for a Union operation and O((m, n)) amortized time for a Find operation, where n is the number of elements and m is the number of operations. Describe a data structure to perform the following operations on an array A[1..n] where initially A[i] = 0 for all i.

A. Given an index i

B. Given an index i, return A[i].

C. Given an index i, return the smallest index j i such that A[j] = 0. Note that such an index always exists since A[n] is always 0. Operations A and B should run in O(1) worst-case time, and operation C should run in amortized time O((m, n)), where m is the number of operations.

1. 10 marks] Recall the Union-Find data structure presented in class that uses tree linking and path compression to achieve O(1) worst case time for a Union operation and O(a(m,n)) amortized time for a Find operation, where n is the number of elements and m is the number of operations Describe a data structure to perform the following operations on an array A[1..n] where initially Ali for all A. Given an index i