A note on data structures for maintaining bipartitions

We consider the following problem: given a ground set U   of elements {1,2,…,n}{1,2,…,n}, and a set SS of bipartitions of U  , design a data structure to support the following three operations: Report(S)Report(S)—report the partition of U   induced by SS, Insert(P,S)Insert(P,S)—add a new bipartition P   to SS, and Delete(P,S)Delete(P,S)—delete the existing partition P   from SS, where the partition of U   induced by SS is given by two elements of U   being in the same class if and only if they are in the same class for every bipartition of SS.We describe a straightforward deterministic data structure with an amortized bound of O(n)O(n) per update, which is optimal.