并查集的路径压缩：并查集优化，让查找更快
并查集用于解决集合合并与元素归属问题（如连通性判断）。核心操作是`find`（查找根节点）和`union`（合并集合），基础版通过`parent`数组记录父节点实现，但长链结构会导致`find`效率极低。为优化，引入**路径压缩**：在`find`过程中，将路径上所有节点直接指向根节点，使树结构扁平化，查找效率接近O(1)。路径压缩通过递归或迭代实现，将长链转化为“一步到位”的短路径。结合按秩合并等优化，可高效处理大规模集合问题，成为解决连通性、归属判断的核心工具。
阅读全文前缀和：前缀和数组如何快速计算区间和？
前缀和数组是一种用于快速计算区间和的辅助数组。定义为：原数组A的前缀和数组S，其中S[0]=0，S[k]（k≥1）是A[1]到A[k]的和，即S[k] = S[k-1] + A[k]。例如原数组A=[1,2,3,4,5]，其前缀和数组S=[0,1,3,6,10,15]。 计算区间和的核心公式是：原数组从第i个到第j个元素的和 = S[j] - S[i-1]。例如计算A[2]到A[4]的和，用S[4]-S[1]=10-1=9，结果正确。 优势在于：预处理S数组需O(n)时间，每次区间和查询仅需O(1)时间，总复杂度O(n+q)（q为查询次数），远快于直接计算的O(qn)。需注意索引对齐（如原数组从0开始时公式调整）、区间合法性及空间换时间的特点。 前缀和数组通过“提前累积”实现
阅读全文