1.

(a) After each update of the non-persistent data structure there are O(log n) nodes, on paths from the updated numbers to the root of the tree, that need to be updated. Therefore in the node-copying persistent data structure we need to make a new copy of each of these nodes, for a total space of O(log n) per update. The query time is the same as in the non-persistent data structure, O(log n) per query.

(b) In the fat node technique, each of the O(log n) updated nodes needs to store information about a new version. Therefore, the space per update is again O(log n). The time per update (using van emde Boaz trees to maintain the version histories within each fat node) is O(log n log log H) where H is the total number of updates that have been performed so far.


2. With the operations we've described priority queues as having, insert and delete-min, there are no queries, and therefore there is nothing useful that one could do with an old partially persistent version of the data structure. So the intended answer is: no, it would not make sense.

If you have a version of priority queues that has a separate find-min operation, you could make it partially persistent by storing a separate list of the minimum value after each update. There would be no need to apply the more complicated fat node or node copying techniques. So with this interpretation the problem could be made to make some sense, although it is still not clear what use it would be to store all those old minima.


3. (a) O(n log n) total space.

(b) O(n) total space.