l. [12] Let ai, a2, . . . , an be a sequence of real numbers, for some n and supports the following operations (S is a given SUM-Box): 1. A SUM-BOX is an ADT that stores the sequence . PARTIAL-SUM(S, m): return 'ni ai, the partial sum from al to am (1 n). m CHANGE(S, i, y): change the value of ai to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(log n). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(log n). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(log n) time while maintaining the attributes stored in the nodes of the AVL tree l. [12] Let ai, a2, . . . , an be a sequence of real numbers, for some n and supports the following operations (S is a given SUM-Box): 1. A SUM-BOX is an ADT that stores the sequence . PARTIAL-SUM(S, m): return 'ni ai, the partial sum from al to am (1 n). m CHANGE(S, i, y): change the value of ai to a real number y. Design a data structure that implements SUM-BOX, using an augmented AVL tree. The worst-case runtime of both PARTIAL-SUM and CHANGE must be in O(log n). Describe your design by answering the following questions. (a) What is the key of each node in the AVL tree? What other attributes are stored in each node? (b) Write the pseudo-code of your PARTIAL-SUM operation, and explain why your code works correctly and why its worst-case running time is O(log n). Let S.root denote the root node of the AVL tree. (c) Describe in clear and concise English how your CHANGE operation works, and explain why it runs in O(log n) time while maintaining the attributes stored in the nodes of the AVL tree