ABSTRACT
In this chapter, we describe advanced data structures and algorithmic techniques, mostly focusing our attention on two important problems: set union and persistence. We first describe set union data structures. Their discovery required a new set of techniques and tools that have proved useful in other areas as well. We survey algorithms and data structures for set union problems and attempt to provide a unifying theoretical framework for this growing body of algorithmic tools. Persistent data structuresmaintain information about their past states and find uses in a diverse spectrum of applications. The body ofwork relating to persistent data structures brings together quite a surprising cocktail of techniques, from real-time computation to techniques from functional programming.
