听起来您正在寻找不连续的数据结构。
给定您的ID集，您的类别会将它们分成不相交的子集。不相交的数据结构通过选择一个代表ID来表示每个类别，该ID将由对其任何成员的查询返回。（被隔离的ID各自构成一个类别，然后返回自己）
对不连续集数据结构的更新结合了任何两个id的类别，以便将来的查询为两个子集的成员返回相同的代表。（如果两个ID已经是同一类别的成员，则该更新在功能上是无操作的）
通常的方法是将每个类别表示为反向树：每个ID都有一个
parent链接，但没有子链接。“代表元素”是树的根，可以通过跟随父链接轻松查询。更新需要找到两个ID的树的根，并且（如果它们不同）通过将一个根作为另一个的父树来合并树。
通过添加几个简单的优化（查询“折叠”查询路径以直接指向根，并且更新始终选择最深树的根作为合并父级），该算法变得非常高效，可以在“
almost-O”中运行（1）摊销时间。
如果要在线访问每个类别中ID的完整列表，则应维护一个附加到每个类别根目录的累积列表，并在每次合并中将它们串联起来。通常，以这种方式维护有关类别的大量统计信息会很方便。
