Trie（字典树）
Trie 是多叉树，每条边代表一个字符，从根到某节点的路径表示一个字符串前缀。常用于前缀匹配、自动补全、拼写检查。
插入：沿路径逐字符建节点，末尾标记为单词结束。查找：沿路径走，若存在且标记则找到。空间 O(总字符数)，单次操作 O(字符串长度)。
压缩 Trie（Patricia Trie）合并单子节点路径，节省空间。双数组 Trie 用两个数组表示转移，适合静态词典、AC 自动机等。
线段树
线段树将区间 [1,n] 递归二分，每个节点代表一个子区间的聚合信息（和、最值等）。叶子对应单点，父节点由子节点合并得到。
单点修改：更新叶子并向上传递。区间查询：若当前节点区间完全包含于查询区间则直接返回，否则递归左右。区间修改用懒标记延迟下传，保证 O(log n)。
应用：区间和、区间最值、区间覆盖、扫描线等。二维可扩展为二维线段树或树套树。
并查集
并查集维护元素的分组，支持合并集合和查询两元素是否同组。用森林表示，每棵树一个集合，根为代表元。
查找：递归找根，路径压缩将路径上节点直接连到根。合并：将一棵树的根接到另一棵的根下，按秩合并时小树接大树。
近似 O(α(n)) 单次操作，α 为反阿克曼函数，实际可视为常数。用于连通分量、最小生成树（Kruskal）、动态连通性等。