ST 表 ST 表（Sparse Table，稀疏表）是一种用于高效解决可重复贡献问题的数据结构，主要用于静态区间查询（如区间最值、区间 GCD 等）。其核心思想是倍增预处理和动态规划，支持 O(nlogn)
线段树 问题 区间信息的维护与查询 写有哪些运算可以使用线段树来维护？ 线段树是一种非常强大的数据结构，它的核心功能是高效地处理区间查询和区间更新操作。线段树能够维护的运算必须满足一个关键性质：结合律。 核心要求：运算满足结合律 对于一个二元运算 ⊕
双连通分量（DCC）——Tarjan 原理 和 SCC 一样都是在 dfs 生成树上记录 dfn 和 low，在环中编号最小的。 需要做一下概念上的区分： SCC（强连通分量） 是针对有向图的概念。一个SCC内的任意两个节点都可以互相到达（即存在双向路径）。 DCC（双连通分量） 是针对无向图的概念
并查集（DSU） 用于快速判断元素是否属于同一个集合。 支持操作 将两个元素放到同一个集合中。 查询两个元素是否属于同一个集合。 代表元素思想 选择一个元素作该集合的代表元素，其他需要添加的元素作为这个代表元素的儿子，形成一颗树。 把判断集合与元素间的从属转化为集合与集合间的关系，通过递归查找。 实
Heavy-Light Decoposition 重链剖分 什么是重链剖分？ 树链剖分 树链剖分是指，将一棵树分成若干条链，使得这些链具有某些性质，使得树上操作变为链上操作和跳链操作（链间操作）。 重链剖分（Heavy-Light Decomposition，简称 HLD）是一种把树分解为若干条链的
树的直径 定义 树的直径是指树中任意两个节点之间的最长路径的长度（边数或距离）。直径的两个端点称为直径端点。 性质与应用 图论基础：用于分析树的结构特征 网络优化：数据中心、通信网络中的延迟评估 算法设计：分治、动态规划的基础 竞技编程：树形DP问题中的常见模式 算法步骤 方法一：两次BFS/DFS
最小生成树（MST）—— Kruskal 贪心策略：每次选择权重最小的边加入生成树，同时避免形成环路 可用于解决最小网络，最低价联通之类的问题 例题 P3366 【模板】最小生成树 #
最近公共祖先 LCA 什么是 LCA 最近公共祖先（Lowest Common Ancestor，简称 LCA）是树上最基础的问题之一：在一棵有根树中，两个节点的所有公共祖先里，深度最大（离根最远）的那个节点，就是它们的 LCA。 举个例子：对于查询 (u,v)
欧拉路问题 Euler Path 欧拉路是图论中的经典问题，源于柯尼斯堡七桥问题。欧拉在 1736 年证明该问题无解，由此开创了图论这一数学分支。 定义 欧拉路径（Eulerian Trail）：通过图中每条边恰好一次的路径（顶点可重复）。 欧拉回路（Eulerian Circuit）：通过图中每条
