一、起源:区间与连通性两类需求

1.1 静态前缀和与差分只能覆盖单一模式

数组上的区间操作有两类基本动作:修改某个位置的值,以及查询某段区间的汇总信息。最朴素的做法是直接遍历,修改 O(1)、区间查询 O(n)。在此基础上,两种预处理手段各把一个方向降到常数级。

前缀和把累加结果预先算好,使区间和查询变成两次前缀相减:

前缀和数组 s[i] = a[1] + a[2] + ... + a[i]

区间和 [l, r] = s[r] − s[l−1]        O(1)

代价:任一元素 a[k] 发生变化,s[k..n] 全部失效,需要重新计算,O(n)

差分是前缀和的逆运算,把「区间修改」变成「两个单点修改」:

差分数组 d[i] = a[i] − a[i−1]

区间加 [l, r] 全部加 v      ⟹  d[l] += v,d[r+1] −= v     O(1)
还原 a[i] = d[1] + d[2] + ... + d[i]                       O(n)

两者都只解决了一侧问题,且这种偏斜不是实现上的疏忽,而是预计算本身的性质:前缀和把「多次查询的公共部分」提前算完,因此一旦数据变动,这份预计算就整体作废;差分把「区间修改的公共部分」提前压缩,因此一旦要读取某个具体位置的值,就必须把压缩还原回来。

前缀和还有第二重限制:它的正确性依赖运算可逆。区间和可以用两个前缀相减,是因为加法存在逆运算减法;若要求的是区间最大值,max 无法通过「前缀最大值相减」还原,前缀和思路直接失效。这条限制会在第二节的合并性质里给出一般判据。

1.2 频繁更新与区间查询并存时的代价

真实场景很少只有单一模式。一份按分钟聚合的监控指标,既要不断写入新的采样点,又要随时回答「最近一小时的请求总量」「某段时间的最大延迟」;一个在线榜单,既要点赞数实时变化,又要查询名次区间内的得分情况。

把两种操作叠加到同一份数据上,前述两种手段都无法同时满足:

n = 10^5 个元素,m = 10^5 次操作(更新与查询各占一半)

用前缀和:每次更新 O(n) → 总代价 O(m·n) = 10^10 次操作,不可用
用差分:  每次查询 O(n) → 同样 O(m·n)
不做预处理:两类操作里有一类必然为 O(n)

需要的是一个折中结构,使两类操作都落在 O(log n)。这个代价不是凭空设定的下界,而是「用一棵高度为 O(log n) 的附加结构承载汇总信息」所能达到的量级;线段树与树状数组都是以这一目标构造的。

1.3 连通性判定中反复搜索的低效

第二类需求与区间无关,但具有相同的形态:维护一组元素之间的关系,并反复回答「两者是否属于同一组」。

典型的表述是等价关系:给定若干条「a 与 b 属于同一类」的事实,判定任意两个元素是否同类。这类关系满足自反、对称、传递三条性质,因此全部事实可以被归结为若干个互不相交的集合。

朴素实现有两条路,代价都集中在反复操作上。

做法一:为每个元素维护一个组编号,合并两组时把其中一组的编号逐个改写
    查询 O(1)
    合并 O(n)          m 次合并累计 O(m·n)

做法二:把关系看作无向图的边,每次查询做一次深度或广度优先搜索
    查询 O(n + m)
    没有把「已经确定的连通性」沉淀下来,重复查询反复付出相同代价

关键缺陷在于信息没有被复用:每一次查询都从零开始重新推导,而答案本可以在合并时逐步维护好。把集合组织成一棵以根节点为代表元的树,使「是否同类」退化为「根是否相同」,并把查询路径上的节点直接连到根,就得到一个查询与合并都接近常数的结构,这就是并查集。

这两类需求构成本篇的两条主线:前者是区间上的汇总信息维护,对应线段树与树状数组;后者是元素间的等价关系维护,对应并查集。两者共享同一个思路——用附加的结构记录已经被压缩过的信息,使重复操作不再从原始数据重新计算。

二、原理

1. 区间问题的分类

在挑选结构之前,需要先把问题本身分类。以下三个维度决定了可用的结构范围。

1.1 静态与动态

静态:数据在预处理之后不再变化,只接受查询
    → 预计算的全部收益都可以保留,前缀和、稀疏表都可行
动态:数据会在查询之间被修改
    → 任何预计算都可能失效,必须使用「修改后能局部修复」的结构

静态与动态的分界决定了对预计算的态度。稀疏表是纯静态结构的典型:它把区间长度为 2^k 的答案全部预存,查询时用两个可重叠的区间拼接出答案,因而只适用于不修改的数据。

1.2 点更新与区间更新

动态问题再按修改的单位细分:

点更新:一次修改单个位置(或单个元素)
区间更新:一次修改一整段连续区间

两者与查询类型组合,共四类:
    点更新 + 点查询      → 普通数组即可,O(1)
    点更新 + 区间查询    → 线段树、树状数组的典型场景
    区间更新 + 点查询    → 差分数组,或树状数组维护差分
    区间更新 + 区间查询  → 线段树的懒标记,或双树状数组

区间更新之所以比点更新更棘手,在于「一次修改涉及多个位置」这一点与预计算的局部性相冲突:线段树能用 O(log n) 完成,靠的是把整段修改记在少数几个覆盖节点上而不逐点下推,这一机制就是懒标记(见 2.4 节)。

1.3 合并性质:结合律与可逆性

区间查询要求把若干子区间的结果拼成整段的结果,因此被维护的运算必须具备可合并性。

结合律: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
    满足结合律才能把区间随意切割后按任意顺序合并,
    这是线段树能递归分治、树状数组能二进制拆分的前提

    加法、乘法、最大值、最小值、按位与或异或、集合合并都满足
    减法、除法、取模不满足(a − (b − c) ≠ (a − b) − c),
    这类运算只能作为「带方向的查询」处理,不能作为区间合并的算子

可逆性是另一条独立的性质,它决定能否用「前缀相减」代替「区间合并」。

可逆:存在逆运算使 (a ⊕ b) ⊖ b = a
    加法可逆(减)、异或可逆(自身)、乘法在模素数下可逆
    最大值不可逆:无法从 max(1..r) 与 max(1..l−1) 反推出 max(l..r)

可逆运算:
    前缀可以支持任意区间查询   [l, r] = pre(r) ⊖ pre(l−1)
    因此树状数组(只能做前缀)也可以支持任意区间和

不可逆运算:
    只能做前缀或整体合并,不能靠相减得到区间
    树状数组无法用于区间最值;区间最值需要线段树,或者静态时用稀疏表

据此可以把常见结构一次性归位:

结构 数据是否可变 支持的更新 支持的查询 运算前提 预处理 单次操作
前缀和 静态 不支持 任意区间和 运算可逆 O(n) O(1)
差分数组 动态 区间加 单点值 运算可逆 O(n) O(1) 更新 / O(n) 查询
稀疏表 静态 不支持 任意区间极值 可重复贡献(幂等) O(n log n) O(1)
线段树 动态 点更新、区间更新 任意区间信息 运算满足结合律 O(n) O(log n)
树状数组 动态 点更新、区间更新 前缀、区间和 运算满足结合律且可逆 O(n) O(log n)
并查集 动态 合并集合 是否同集合 等价关系 O(n) 摊还 O(α(n))

「可重复贡献」是稀疏表特有的前提:要求 a ⊕ a = a(如 max、min、gcd、按位与),这样才能让查询用的两个覆盖区间重叠而不出错。

2. 线段树

2.1 节点表示区间与分治结构

线段树把整个下标区间 [1, n] 二分,得到一棵以区间为节点的二叉树:

对节点代表的区间 [l, r]:
    若 l = r,节点为叶子,对应单个元素
    否则取中点 mid = ⌊(l + r) / 2⌋,把区间分为 [l, mid] 与 [mid+1, r]
    分别递归构造左、右子节点

每个节点维护它所代表区间的合并信息
父节点的信息由其左右子节点的信息合并得到
n = 8 时区间 [1, 8] 的划分:

                     [1, 8]
                  /          \
             [1, 4]            [5, 8]
            /      \          /      \
        [1, 2]   [3, 4]   [5, 6]   [7, 8]
        /   \    /   \    /   \    /   \
      [1]  [2] [3]  [4] [5]  [6] [7]  [8]

这一结构带来了两个直接后果,它们正是区间查询能落在 O(log n) 的原因。

任意区间可以被拆成 O(log n) 个节点的并。 从根向下定位查询区间 [ql, qr],每层的处理方式只有三种,其中只有「部分覆盖」的节点需要继续递归,而每一层部分覆盖的节点最多两个(区间被分成左右两半,最多只有一处在跨越中点)。因此总访问节点数不超过 2⌈log₂n⌉。

任意单点的修改只影响它到根的这条路径。 点更新把叶子改掉后,只需沿父链把信息重新合并一次,路径长度为树高 O(log n)。

2.2 数组表示与 4n 空间的由来

线段树是完全二叉树的形态,父子关系可由下标算术给出,因此不需要任何引用字段。采用 1-based 编号(便于用 node << 1 与 node << 1 | 1):

节点 node 代表区间 [l, r],mid = (l + r) / 2
    左子节点 node * 2    代表 [l,   mid]
    右子节点 node * 2 + 1 代表 [mid+1, r]

根节点编号 1,代表 [1, n]
叶子节点代表单元素区间

空间大小取 4n 是常用做法,理由来自节点数的最坏情况。设 n 个元素的线段树节点数为 f(n):

f(1) = 1
f(n) = f(⌈n/2⌉) + f(⌊n/2⌋) + 1

n 为 2 的幂时:f(n) = 2n − 1(满二叉树,第 k 层 2^k 个节点)
n 不是 2 的幂时:左右子树规模不等,树底参差不齐,
                 编号不再连续,最深叶子的下标可能超过 2n

可归纳得到 f(n) ≤ 4n − 1

实际使用的下标不是节点个数,而是最深叶子的编号。当 n 略大于某个 2 的幂时,树会向右侧多延伸一层,最深叶子的编号接近 4n,因此按编号开数组必须取 4n 这一上界;取 2n 会在 n 不是 2 的幂时越界。另一种做法是先把 n 向上补齐到 2 的幂 size = 2^⌈log₂n⌉,用 2 * size 个槽位、叶子放在 [size, size + n),容量同样够用,且后续可以写成迭代形式(见第三节 1.4 节)。

两种容量取法的对照:

4n 方案(递归实现常用)
    下标从 1 开始,区间 [1, n] 严格二分
    容量 4n,有冗余但实现最直观

2 * 2^⌈log₂n⌉ 方案(迭代实现常用)
    叶子统一在第 ⌈log₂n⌉ + 1 层,编号连续
    n = 10^5 时 size = 131072,容量 262144 ≈ 2.6n,比 4n 更省

需要区分的是容量与节点数:实际节点数为 O(n),另外的空间是编号不连续造成的空槽。

2.3 点更新与区间查询

点更新沿根到叶的路径下行,回溯时自底向上重新合并:

update(node, l, r, pos, v):
    若 l = r(到达叶子)
        更新 tree[node]
        返回
    mid = (l + r) / 2
    若 pos ≤ mid  → 递归左子节点
    否则          → 递归右子节点
    tree[node] = merge(左子, 右子)      // 回溯时合并

代价为一条根到叶的路径,即 O(log n);被访问节点的总数是树高。

区间查询把查询区间拆解到节点上,三类情况对应三种处理:

query(node, l, r, ql, qr):
    若 [l, r] ∩ [ql, qr] = ∅   (完全不相交)
        返回单位元(如区间和返回 0,区间最值返回 ±∞)
    若 ql ≤ l 且 r ≤ qr       (完全覆盖)
        直接返回 tree[node],不再进入子树
    否则                       (部分覆盖)
        递归左右子树,把两个结果合并后返回

「单位元」的选取必须与合并运算匹配:加法用 0,最大值用 −∞,最小值用 +∞,集合合并用空集。单位元的错误会影响边界——用 0 作为最大值查询的单位元,会把负值区间错判为 0。

复杂度为 O(log n):每一层最多有两个节点落入「部分覆盖」,层数为 O(log n)。这一点与「把区间拆成 O(log n) 段」是同一事实的两种表述。

2.4 懒标记与区间更新

区间更新若逐点执行,代价退化为 O(n)(涉及区间的长度)。懒标记(lazy tag)的做法是把「对这一整段区间的修改」记录在完全覆盖的节点上,暂不向下传递。

标记的含义:该节点维护的值已经反映了这次修改,
            但它的子节点尚未应用这次修改。

因此节点上同时保存两类信息:
    tree[node]   该区间在当前全部修改作用下的正确汇总值
    lazy[node]   尚未下推给子节点的修改

下推(pushdown)的时机是进入子节点之前,顺序必须是「先下推、再递归」:

void pushDown(node, l, r):
    若 lazy[node] 为空 → 直接返回
    mid = (l + r) / 2
    apply(左子节点, l,   mid, lazy[node])    // 更新左子的值,并叠加左子的标记
    apply(右子节点, mid+1, r, lazy[node])    // 更新右子的值,并叠加右子的标记
    lazy[node] = 空                          // 标记已交给子节点,必须清除

apply(node, l, r, v) 做两件事,缺一不可:

tree[node] 按区间长度更新:tree[node] += v * (r − l + 1)
lazy[node] 叠加新标记:    lazy[node] += v

只更新 tree 而不更新 lazy,会在后续下推时丢失这次修改;只更新 lazy 而不更新 tree,则当前节点的查询结果不含这次修改。这两类错误都表现为「部分查询结果偏小或偏大,且只在有区间更新之后出现」。

标记的复合方式由运算决定,这也是懒标记实现中最容易出错的一处:

运算 apply 对 tree 的作用 标记的复合方式 下推后父标记
区间加 tree += v * len 加法叠加 lazy += v 置 0
区间赋值 tree = v * len 覆盖 lazy = v(旧标记被丢弃) 置为「无标记」
区间加后区间赋值 依上两行分别处理 赋值标记会清除同节点的加法标记 —

赋值与加法的混合是常见考点:若节点上已有加法标记,再来一次赋值,赋值会覆盖先前的加法效果,因此必须把旧的加法标记清空,否则下推时会把已被覆盖的加法又加一遍。标记复合的顺序不可交换,实现时必须明确每种操作的语义顺序。

适用懒标记的合并运算需要额外满足一条:区间更新作用于整个区间的方式与区间长度相关(如区间加、区间赋值),才能由长度算出对汇总值的影响。对于区间最值配合区间加,还需要记录该区间内实际被加了多少次才能正确更新极值(或改用标记永久化),这类组合的实现复杂度显著高于区间和。

2.5 离散化处理大值域

线段树的数组容量由坐标范围决定(下标区间 [1, n]),而实际问题中的坐标常常远大于元素个数:坐标可能取到 10^9,但只有 10^5 个不同的取值。

原始坐标: [10^9, 5, 10^9 + 7, 3]        值域 10^9,无法直接开数组
去重排序: [3, 5, 10^9, 10^9 + 7]        用排名 1..m 代替原值
映射:     3 → 1,5 → 2,10^9 → 3,10^9 + 7 → 4

离散化保留了坐标之间的大小关系与相对次序,因此所有区间操作(求区间和、判断包含关系)的语义不变,而结构规模从值域降为元素个数。查询某个坐标时用二分在该有序数组里定位排名,代价 O(log m)。

两个必须注意的点:

  • 只对「出现过的坐标」离散化。若区间的端点本身也是坐标(如询问 [L, R] 中有多少个点,L、R 可能不是已出现的点),则需把 L、R 也一并加入待离散化的集合,否则端点无法定位。
  • 输出必须映射回原值。离散化只用于内部下标,任何对外输出的坐标、区间长度、相对距离都要用原值,映射遗漏会产生「整数看起来正确、语义完全错误」的结果。区间长度尤其容易出错:离散化后的 r − l + 1 是排名之差,不等于原坐标之差。

2.6 合并信息的设计

线段树每个节点维护什么信息,由「父节点能否由左右子节点推出」这一要求决定。常见设计的复杂度随问题不同而上升。

单值信息(和、最值、计数、异或和)最容易:父节点直接由两个子节点的同一字段合并。

带前缀与后缀的信息需要多维护几个字段。以「区间内最长连续 1 的个数」为例,若只记录最长长度,父节点无法由左右子节点的最长长度直接得出——跨越中点的连续段需要知道左子节点右端与右子节点左端的连续情况。因此每个节点要维护四个量:

len  :区间长度
pre  :从区间左端开始的最长连续 1 的个数
suf  :从区间右端开始的最长连续 1 的个数
best :区间内最长连续 1 的个数

合并(左子 L,右子 R):
    len  = L.len + R.len
    pre  = (L.pre == L.len) ? L.len + R.pre : L.pre
    suf  = (R.suf == R.len) ? R.len + L.suf : R.suf
    best = max(L.best, R.best, L.suf + R.pre)     // 跨越中点的连接段

要点是 best 的第三项 L.suf + R.pre——完全落在左或右子节点内部的答案已经由 L.best 与 R.best 覆盖,只有跨越分界点的连续段需要额外拼接。合并信息的最小充分集,就是「使父节点能被唯一推出」的最少字段数;字段不足会造成合并结果错误,字段冗余则浪费空间与维护成本。

同类设计还包括区间最大子段和(维护区间和、最大前缀和、最大后缀和、最大子段和)与括号序列匹配长度(维护未匹配的左括号数、未匹配的右括号数与匹配对数)。这些问题的共同特征是:答案可能跨越区间边界,因此必须把边界处的情况作为独立字段保存。

3. 树状数组

3.1 二进制拆分与 lowbit

树状数组用另一种方式分解前缀:把前缀长度按二进制拆成若干个 2 的幂之和。

前缀长度 x 的二进制分解(从低位到高位依次剥离最低位的 1):

x = 13 = 1101₂
    1101₂ 去掉最低位 1 → 1100₂ = 12
    1100₂ 去掉最低位 1 → 1000₂ = 8
    1000₂ 去掉最低位 1 → 0000₂ = 0
即 13 = 8 + 4 + 1,对应区间 [1,8]、[9,12]、[13,13]

分解出的区间个数 = x 的二进制中 1 的个数 ≤ ⌈log₂(x+1)⌉

lowbit 是执行这一剥离的运算,取值为「最低位的 1 及其之后的全部 0」:

lowbit(x) = x & (−x)        取最低位的 1
lowbit(13) = 13 & (−13) = 0001₂ = 1
lowbit(12) = 12 & (−12) = 0100₂ = 4
lowbit(8)  = 8  & (−8)  = 1000₂ = 8

原理:−x 在补码下等于 (x 取反) + 1,
      这会把 x 最低位的 1 保留下来,并把其右侧的 0 变成 1(左侧全部取反)
      两者按位与,只留下最低位的那个 1。

由此定义数组 c[x],它维护的区间是 (x − lowbit(x), x],即「以 x 结尾、长度为 lowbit(x) 的一段」:

x  =  1  lowbit = 1  c[1]  维护 [1, 1]
x  =  2  lowbit = 2  c[2]  维护 [1, 2]
x  =  3  lowbit = 1  c[3]  维护 [3, 3]
x  =  4  lowbit = 4  c[4]  维护 [1, 4]
x  =  5  lowbit = 1  c[5]  维护 [5, 5]
x  =  6  lowbit = 2  c[6]  维护 [5, 6]
x  =  7  lowbit = 1  c[7]  维护 [7, 7]
x  =  8  lowbit = 8  c[8]  维护 [1, 8]

c[x] 维护的区间长度等于 lowbit(x),这一对应关系解释了树状数组的全部操作。

3.2 点更新与前缀查询

点更新:修改 a[i] 会影响所有包含 i 的区间,即「维护区间左端点 ≤ i 且 x ≥ i」的那些 c[x]。这些 x 恰好是 i 沿 lowbit 方向逐次向上跳的结果。

void add(i, v):
    while (i <= n):
        c[i] += v
        i += lowbit(i)          // 跳到下一个包含它的区间

i = 5 → 6 → 8 → ...     每次跳过的长度依次增大

前缀查询:累加前缀 [1, i] 只需把 i 二进制分解出的几个区间相加。

long prefixSum(i):
    s = 0
    while (i > 0):
        s += c[i]
        i −= lowbit(i)          // 剥离最低位的 1

i = 13 → 12 → 8 → 0     累加 c[13](即 [13,13])、c[12]([9,12])、c[8]([1,8])

两个循环的方向相反:更新沿 i += lowbit(i) 上行,查询沿 i −= lowbit(i) 下行。循环次数都等于 i 的二进制位数,即 O(log n)。

任意区间和由两次前缀相减得到:[l, r] = prefixSum(r) − prefixSum(l−1)。

3.3 与线段树的适用边界

树状数组是线段树在特定运算下的紧凑实现,两者的适用边界由三点决定。

运算可逆性。树状数组只能直接回答「前缀」,任意区间查询依赖前缀相减,因此运算必须可逆。对区间最大值这类不可逆运算,树状数组无法支持任意区间查询(只能回答从起点开始的前缀最值,且要求元素单调不减,否则无法在删除时回退)。线段树把区间信息直接维护在节点上,对不可逆运算同样有效。

常数与实现成本。树状数组的每次操作只做 O(log n) 次加法与下标跳转,循环体内没有函数调用与递归;线段树的每次操作需要递归或迭代遍历多层节点,并伴随 pushdown、pushup、边界判断。同一量级下树状数组的常数因子通常更小,代码长度也显著更短(建树可复用 add)。仅做点更新加区间和的场景,树状数组是更直接的选择;需要区间更新、区间最值、自定义合并信息时,线段树的表达力更强。

功能覆盖。树状数组可表达的合并信息比线段树窄。它要求 c[x] 能由更小的区间合并得到,并且更新路径上的所有 c[x] 都能正确增量更新——这对加法、异或这类可减运算成立,对带前缀与后缀的复杂信息(如最长连续段)不成立。对于这类问题,只能使用线段树(或分块)。

维度 树状数组 线段树
点更新 + 前缀/区间和 支持,常数小 支持,常数大
点更新 + 区间最值 不支持任意区间(不可逆) 支持
区间更新 + 区间查询 支持(差分技巧,见 3.4 节) 支持(懒标记)
复杂合并信息(最长连续段等) 不支持 支持
空间 O(n) O(4n) 或 O(2·2^⌈log₂n⌉)
实现长度 短,循环即可 长,需要处理标记与边界
非递归友好度 天然迭代 点更新可迭代,区间更新受限

3.4 区间更新与区间查询的差分技巧

树状数组本身只做点更新,但把「维护对象」从原数组换成差分数组,就可以表达区间更新。

区间加 + 单点查询。 设差分数组 d[i] = a[i] − a[i−1],则 a[i] = d[1] + d[2] + ... + d[i],即单点值等于差分的前缀和。区间加 [l, r] 加 v 转化为两个点更新:

d[l]   += v
d[r+1] −= v

单点查询 a[i] = prefixSum(i)

区间加 + 区间和。 直接对差分求一次前缀和只能拿到单点值,区间和需要对单点值再求和。把 a[i] = Σ_{j≤i} d[j] 代入区间和:

Σ_{i=1..x} a[i] = Σ_{i=1..x} Σ_{j=1..i} d[j]
               = Σ_{j=1..x} d[j] · (x − j + 1)      (交换求和次序,d[j] 被累加了 x−j+1 次)
               = (x + 1) · Σ_{j=1..x} d[j] − Σ_{j=1..x} j · d[j]

因此维护两个树状数组,分别存放 d[j] 与 j · d[j],区间和可用两个前缀各一次查询组合得到。区间加 [l, r] 加 v 时,两个数组各做两次点更新:

t1: d[l] += v,  d[r+1] −= v
t2: l·d[l] += v·l,  (r+1)·d[r+1] −= v·(r+1)

前缀 a[1..x] 的和 = (x + 1) · t1.prefixSum(x) − t2.prefixSum(x)
区间 [l, r] 的和   = 前缀 r 与 前缀 l−1 相减

这一技巧把「区间更新 + 区间求和」也纳入了树状数组的适用范围,代价是维护两个数组、写两倍的点更新,实现上仍比带懒标记的线段树简洁。

4. 并查集

4.1 把等价关系维护为森林

并查集(Disjoint Set Union,DSU)处理的是等价关系的动态维护。等价关系满足三条性质:

自反性:a 与 a 属于同一集合
对称性:a 与 b 同类 ⟹ b 与 a 同类
传递性:a 与 b 同类、b 与 c 同类 ⟹ a 与 c 同类

这三条性质使所有事实可以被归结为若干个互不相交的集合,问题因此变成「判断两个元素是否落在同一集合」以及「把两个集合合并成一个」。

实现方式是把每个集合表示为一棵有根树,用根节点作为该集合的代表元:

每个元素保存一个 parent 指针,指向同集合中的另一个元素
树的根节点 parent 指向自身
同一集合 ⟺ 两者的根相同

find(x)  沿 parent 上溯到根
union(a, b)  找到两个根,把其中一个根的 parent 指向另一个根

判断依据是:find 的时间与树高成正比,union 的时间为两次 find。因此全部优化都围绕降低树高。

4.2 路径压缩

find 是唯一需要遍历路径的操作,因此可以在遍历时顺手把路径上的节点直接连到根:

int find(x):
    若 parent[x] == x → 返回 x
    root = find(parent[x])       // 先递归到根
    parent[x] = root             // 回溯时把 x 挂到根上
    返回 root

效果是把树「压扁」:第一次查找后,路径上的节点都成为根的直接子节点,后续查找只需两次访问。

查找 7(链式结构 7 → 6 → 5 → 4 → 1,1 为根):

压缩前: 7 → 6 → 5 → 4 → 1        代价 4 次上溯
压缩后: 7 → 1,6 → 1,5 → 1,4 → 1
再查 7:代价 1 次上溯

路径压缩是摊还意义上的优化,不保证单次操作快:遇到深链时那一次 find 仍然要走完整条链。关于摊还代价的口径与三种论证方法,见 复杂度与算法分析 的摊还分析一节。同时,路径压缩会修改树的结构,因此不适用于需要回溯或持久化的场景。

4.3 按秩合并与按大小合并

路径压缩减少的是「被查找过的路径」的高度,对从未被查找的部分没有帮助。第二条优化直接控制合并后的树高:合并时不随意指定根,而是把矮的树挂到高的树上。

按秩(rank)合并:rank 记录树高的上界(不是精确高度)
    合并时把 rank 较小的一方挂到 rank 较大的一方
    仅当两者 rank 相等时,新根的 rank 加一

按大小(size)合并:size 记录集合中元素个数
    合并时把元素少的一方挂到元素多的一方
    新根的 size 为两者之和

两种做法都能给出 O(log n) 的树高上界,论证方式是把「rank(或 size)翻倍」与「上溯一层」绑定:一个节点的深度每增加 1,其所在集合的规模至少翻倍,因此深度不超过 ⌊log₂n⌋。

按大小合并还有一个附带好处:根的 size 就是集合的元素个数,可以直接回答「这个集合有多少元素」,无需额外遍历。需要这一信息的场景下优先选按大小合并。

4.4 两个优化叠加后的近似常数复杂度

单独使用路径压缩或按秩合并,树高上界都是 O(log n)。两者同时使用时,结论显著更强:

n 次操作的序列,总代价为 O(n · α(n)),摊还每次 O(α(n))

α 为反阿克曼函数:
    α(10^80) ≈ 4,在一切可想象的规模下都不超过 4
    因此工程上可以按常数处理

需要注意结论的精确表述:摊还 O(α(n)) 而非 O(1),只是 α 的增长极其缓慢。引用这一结论时应当同时说明三点,这与 复杂度与算法分析 中对摊还结论的使用边界一致:

  • 结论针对操作序列的总代价,不约束单次 find 的最坏代价;
  • 结论依赖「树高受秩的上界限制、路径压缩只降低后续查找代价」这一结构不变量;
  • 一旦引入撤销能力(可持久化并查集),该摊还结论不再成立。

4.5 带权并查集与种类并查集

基本并查集只维护「是否同类」这一布尔信息。当关系本身带有可累加的权值时,需要在压缩与合并时同步维护权值。

带权并查集为每个节点保存一个到父节点的权值,记为 w[x],满足 val[x] = val[parent[x]] + w[x](根的 w 恒为 0)。典型场景是「带偏移的关系」:一个单调队列中元素与其前一个元素的距离、某人与直接上级的职级差。

find 时路径压缩需要同步更新权值:
    先递归拿到根,此时 parent[x] 已指向根、w[parent[x]] 已是「旧父到根」的偏移
    再把 w[x] += w[parent[x]],得到「x 到根」的偏移
    最后 parent[x] = root

合并时由已知的关系解出新根之间的权值,公式见第三节 3.4 节

种类并查集处理的是「关系有多类」的情形,如「朋友与敌人」「同类与捕食与被捕食」。两种实现方式:

方式一:扩展域(用 k 倍节点)
    把每个元素拆成 k 个虚拟节点,分别代表它在 k 种关系中的取值
    敌人关系 = 把 a 的「朋友域」与 b 的「敌人域」合并
    食物链(3 类)用 3n 个节点,把关系翻译成跨域的合并与约束检查
    优点:不需要维护权值,逻辑直观;缺点:节点数乘以 k

方式二:带权并查集
    用权值模 k 表示两个元素的关系类别
    k = 2 时权值 0 表示同类、1 表示异类
    合并时对权值做模 k 运算即可

两者的表达能力相当,扩展域更容易正确实现,带权版更省空间。选择依据通常是 k 的大小与实现者对该问题的熟练程度。

5. 对比与选型

把全部结构放在同一张表中对照。表中「实现复杂度」指代码量与出错面的综合感受,是相对判断。这些结构承载的是同一组操作语义(区间汇总、集合合并)在不同存储方案下的实现,抽象与实现分离的视角见 抽象数据类型(ADT)。

结构 更新频率支持 查询类型 预处理 单次操作 空间 实现复杂度
直接遍历 任意 任意区间 无 O(1) 更新 / O(n) 查询 O(n) 最低
前缀和 不支持更新 任意区间和 O(n) O(1) O(n) 低
差分数组 区间加 单点值 O(n) O(1) 更新 / O(n) 查询 O(n) 低
稀疏表 不支持更新 任意区间极值 O(n log n) O(1) O(n log n) 低
树状数组 点更新、区间加 前缀、任意区间和 O(n) O(log n) O(n) 中
线段树(递归) 点更新、区间更新 任意区间信息 O(n) O(log n) O(4n) 高
线段树(迭代) 点更新 任意区间信息 O(n) O(log n) O(2·2^⌈log₂n⌉) 中
并查集 合并集合 是否同集合 O(n) 摊还 O(α(n)) O(n) 中

选型顺序可以固定为四步:

1. 数据是否会被修改?不会 → 前缀和(区间和)或稀疏表(区间极值),O(1) 查询
2. 只有区间更新、没有区间查询? → 差分数组
3. 需要修改,且运算可逆、只需区间和? → 树状数组(代码短、常数小)
4. 需要区间更新与区间查询并存,或运算不可逆,或合并信息复杂? → 线段树
5. 问题与区间无关,而是维护元素的等价关系? → 并查集

第 3、4 步的取舍是这篇内容中最常被讨论的一处:树状数组在「点更新 + 区间和」上全面优于线段树,但一旦运算不可逆(区间最值)或需要复杂合并信息(最长连续段),它的表达力不足,必须换成线段树。反过来,能用树状数组时不应引入线段树——多出的实现复杂度没有换来任何能力。

6. 典型问题模型

6.1 区间和、区间最值、区间计数

三类问题对应三种不同的合并运算,也对应不同的结构选择。

区间和: 合并算子为加法,可逆 → 树状数组或线段树均可
区间最值:合并算子为 max / min,不可逆 → 线段树;静态时可用稀疏表
区间计数:合并算子为加法,每个元素对计数的贡献为 0 或 1
          (如统计区间内满足某条件的元素个数)→ 树状数组或线段树

「区间计数」有一个变体值得单独提出:把条件从「元素是否满足某属性」换成「某个值是否出现过」。此时把原数组视为「位置到值的映射」,查询变成「区间内有多少种不同的值」。这类问题的常见做法是把每个值只在它最后一次出现的位置上计 1,然后把查询按右端点排序离线处理,退化为普通的区间计数。离线 + 排序 + 树状数组是区间统计中反复出现的组合模式。

6.2 区间合并信息(最长连续区间)

要求维护区间内最长的一段满足条件的连续元素,如「最长的连续 1」「最长的连续空位」「最长的连续达标区间」。这一模型的特征是答案可能跨越分界点,因此节点必须按 2.6 节的方式同时维护前缀、后缀与整体最优三个量。

典型应用包括:

内存分配:在一段地址空间中找长度足够的连续空闲块
泊位与座位分配:找连续的若干相邻空位
信号与状态分析:求最长的连续达标(或超标)时间窗口
二进制数组的处理:最长连续 1、最大连续区间

这一模型与「区间和」的对比很好地说明了合并信息设计的重要性:两者都是线段树上的应用,但前者需要 4 个字段、合并逻辑包含跨中点判断,后者只需 1 个字段。不能把区间和的做法直接套用到最长连续段上,这是线段树类题目最常见的错误来源。

6.3 动态连通性与朋友圈问题

并查集最直接的应用是维护「若干对关系构成的连通性」,并在关系不断增加的过程中随时回答连通性问题。

问题形式:
    给出 n 个节点与若干条「二者相连」的事实
    随事实的加入,回答任意两点是否已经连通,或最终有多少个连通块
    变体:朋友的朋友是朋友,求最大朋友圈的规模

实现:
    每条事实执行一次 union,两个根不同则合并、连通块数减一
    连通块数初始为 n,每次成功合并减 1
    集合规模用按大小合并的根上 size 字段直接读取

要点是并查集只支持合并而不支持分裂:一旦两个集合合并,无法再拆开。需要支持删除边或分裂的场景(如动态图连通性)不能用基本并查集,须改用其他结构。这一限制的来源是并查集把信息压缩成「根相同」这一个不可逆的判定。

6.4 等价类划分与冲突检测

一组「相等 / 不等」的约束可以转化为两类操作,并查集恰好能按顺序处理:

给定若干约束:a = b、c = d、a ≠ c ...
1. 先处理全部「相等」约束,执行 union
2. 再逐条检查「不等」约束:若两端已经同根,则约束矛盾,整体无解

这一「先合并、再校验」的顺序是关键:若一边合并一边校验,可能在校验时尚未看到能把两个元素合并起来的相等约束,从而误判为无冲突。把同类型约束集中处理,避免判定依赖处理顺序,是这类问题的通用做法。

典型应用是约束满足类问题与数据一致性校验:一组字段声明了彼此的相等与不等关系,判断是否存在矛盾。

6.5 图中的连通分量

无向图的连通分量与并查集描述的是同一个数学对象:把每个顶点看作元素,每条边看作「两个端点属于同一分量」的事实,则并查集维护的集合正是连通分量。

对图的每条边执行 union(u, v)
处理结束后,每个连通分量对应一棵树,根相同的顶点属于同一分量
统计不同根的个数即连通分量数

代价 O(m · α(n)),优于对每个顶点做一次搜索的 O(n · (n + m))

需要区分的是适用条件:并查集只处理边的加入(增量式连通性),从零开始加完全部边后回答静态连通分量是它的强项;若边会动态增删,或在处理过程中需要遍历具体路径与分量内的顶点,则应当使用图的遍历算法(深度优先、广度优先)来获得完整的分量结构。两者关注的对象不同:并查集回答「是否同属一个集合」,图遍历回答「集合具体由哪些顶点与边构成」。图的表示方法、深度优先与广度优先遍历、访问标记的时机见 图的表示与遍历。

三、实现

1. 线段树实现要点

1.1 建树、查询与点更新的递归实现

以「区间加 + 区间和」为例,节点同时保存区间和与加法懒标记。区间约定为闭区间 [l, r],下标从 1 开始。

class SegmentTree {
    private final int n;
    private final long[] tree;   // 节点维护的区间和
    private final long[] lazy;   // 区间加的懒标记

    SegmentTree(int[] a) {
        n = a.length;
        tree = new long[4 * n + 1];
        lazy = new long[4 * n + 1];
        build(1, 1, n, a);
    }

    // 由左右子节点的值合并出当前节点
    private void pushUp(int node) {
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }

    // 把区间加的修改作用到 node 上:值按区间长度更新,标记叠加
    private void apply(int node, int l, int r, long v) {
        tree[node] += v * (r - l + 1);
        lazy[node] += v;
    }

    // 把 node 的标记下推给两个子节点;必须在递归子节点之前调用
    private void pushDown(int node, int l, int r) {
        if (lazy[node] == 0) {
            return;                          // 无待下推的标记
        }
        int mid = (l + r) >>> 1;
        apply(node << 1, l, mid, lazy[node]);
        apply(node << 1 | 1, mid + 1, r, lazy[node]);
        lazy[node] = 0;                      // 标记已交给子节点,必须清除
    }

    private void build(int node, int l, int r, int[] a) {
        if (l == r) {
            tree[node] = a[l - 1];           // a 为 0-based,下标换算
            return;
        }
        int mid = (l + r) >>> 1;
        build(node << 1, l, mid, a);
        build(node << 1 | 1, mid + 1, r, a);
        pushUp(node);
    }

    // 区间加:ql..qr 全部加 v
    void update(int node, int l, int r, int ql, int qr, long v) {
        if (ql <= l && r <= qr) {            // 完全覆盖:打标记返回,不进入子树
            apply(node, l, r, v);
            return;
        }
        pushDown(node, l, r);                // 先下推,再递归
        int mid = (l + r) >>> 1;
        if (ql <= mid) {
            update(node << 1, l, mid, ql, qr, v);
        }
        if (qr > mid) {
            update(node << 1 | 1, mid + 1, r, ql, qr, v);
        }
        pushUp(node);                        // 回溯时合并
    }

    // 区间和查询
    long query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return tree[node];
        }
        pushDown(node, l, r);                // 查询同样要下推,否则子节点的值不含祖先标记
        int mid = (l + r) >>> 1;
        long res = 0;
        if (ql <= mid) {
            res += query(node << 1, l, mid, ql, qr);
        }
        if (qr > mid) {
            res += query(node << 1 | 1, mid + 1, r, ql, qr);
        }
        return res;
    }
}

点更新只是区间更新的特例(令 ql = qr = pos 且 v 为增量),因此不单独实现;若原意是「把 a[pos] 改为 v」,先求出旧值再传入差值,或改用赋值标记。

1.2 懒标记的维护与下推顺序

前一段代码中三处顺序要求,任一处颠倒都会产生错误结果:

顺序一:先 pushDown,再递归子节点
    若先递归再下推,子节点在计算时尚未获得祖先的标记,结果偏小

顺序二:pushDown 内先更新子节点的 tree 与 lazy,最后清除父节点的 lazy
    若先清除父标记,则这次修改永久丢失

顺序三:递归返回后调用 pushUp
    若忘记 pushUp,父节点的值不再等于两个子节点之和,
    后续在这段区间上的查询会读到过期值

pushDown 在查询路径上同样需要调用。这一点容易被忽略:查询只读不写,看起来与标记无关,但被查询区间的部分节点可能只收到了祖先的标记而没有更新自身,此时直接读取 tree[node] 会得到旧值。

赋值类标记的下推需要额外注意:apply 应当把子节点的标记覆盖而不是叠加,同时在父节点上以赋值覆盖原有的加法标记。若实现中两种标记共用一个数组,必须为「无标记」保留一个可区分的状态(如用额外布尔数组或哨兵值),否则无法区分「标记为 0 的加法」与「无标记」。

1.3 数组下标与区间的边界处理

几处约定必须在实现之前确定,且在整个实现中保持一致。

下标基准:树节点编号与区间下标都从 1 开始
    便于用 node << 1 与 node << 1 | 1 表示子节点
    数组容量取 4n + 1,多留一格避免 node = 4n 时的越界

中点的取法:mid = (l + r) / 2(向下取整)
    左区间 [l, mid]、右区间 [mid+1, r] 必须无重叠、无遗漏
    写成 [l, mid - 1] 与 [mid, r] 会造成死循环或区间丢失

区间开闭:统一使用闭区间 [l, r]
    若内部用半开区间 [l, r),则叶子判定为 l + 1 == r、查询条件改为 ql < r && l < qr
    两种口径不能混用,混用会产生「差一个元素」的结果

与查询区间的比较:
    左子节点需要递归 ⟺ ql <= mid
    右子节点需要递归 ⟺ qr > mid
    写成 ql < mid 或 qr >= mid 会漏掉恰好落在中点的元素

溢出处理:(l + r) >>> 1 与 l + (r - l) / 2 等价,
    在 l、r 为 int 时后者更安全;使用 >>> 保证负数移位语义一致

1.4 非递归实现思路与限制

线段树也可以写成迭代形式,思路是把树补成满二叉树,叶子统一放在同一层:

// 容量取不小于 n 的 2 的幂,叶子放在 size + i
int size = 1;
while (size < n) {
    size <<= 1;
}
long[] t = new long[2 * size];

// 建树:先写叶子,再自底向上合并
for (int i = 0; i < n; i++) {
    t[size + i] = a[i];
}
for (int i = size - 1; i > 0; i--) {
    t[i] = t[i << 1] + t[i << 1 | 1];
}

// 点更新:a[p] 加上 v,沿父链重新合并
void update(int p, long v) {
    int i = p + size;
    t[i] += v;
    for (i >>= 1; i > 0; i >>= 1) {
        t[i] = t[i << 1] + t[i << 1 | 1];
    }
}

// 区间和查询:[l, r) 半开区间
long query(int l, int r) {
    long res = 0;
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
        if ((l & 1) == 1) res += t[l++];       // l 是右子节点,整段纳入
        if ((r & 1) == 1) res += t[--r];       // r - 1 是左子节点,整段纳入
    }
    return res;
}

要点与限制:

优点:
    没有递归,常数显著小于递归版
    查询从两个端点同时向根收缩,每层最多纳入两个完整节点

限制一:查询区间必须写成半开区间 [l, r)
    循环的不变量依赖这一点;写成闭区间需要额外调整端点

限制二:区间更新难以直接写成非递归
    带懒标记的区间更新需要在「从根到被修改节点」的路径上逐层下推,
    而下推依赖自顶向下的顺序,迭代写法需要在循环前先收集路径并正向下推
    折中的做法是标记永久化:不在下推时修改子节点,而是在查询路径上累加沿途标记

限制三:合并运算必须满足结合律,且当区间为空时返回单位元

因此迭代形式主要适用于「点更新 + 区间查询」;一旦涉及区间更新与复杂标记,递归实现的清晰度更值得保留。

2. 树状数组实现要点

2.1 lowbit 计算与下标约定

class Fenwick {
    private final int n;
    private final long[] c;          // c[i] 维护区间 (i - lowbit(i), i]

    Fenwick(int n) {
        this.n = n;
        this.c = new long[n + 1];
    }

    // 取最低位的 1 及其后的 0;x 为 0 时结果为 0
    private static int lowbit(int x) {
        return x & (-x);
    }
}

几点约定:

下标从 1 开始,c[0] 不使用(lowbit(0) = 0,会使循环无法推进)
lowbit 依赖补码语义,只对非负整数有效;
    Python 等语言需显式写成 x & (-x),注意整数为任意精度、不涉及补码溢出
Java 中 x & (-x) 与 x & (~x + 1) 等价,前者更简洁

2.2 点更新与前缀查询

// 单点加:a[i] 加上 v
void add(int i, long v) {
    for (; i <= n; i += lowbit(i)) {
        c[i] += v;
    }
}

// 前缀和:a[1] + ... + a[i]
long prefixSum(int i) {
    long s = 0;
    for (; i > 0; i -= lowbit(i)) {
        s += c[i];
    }
    return s;
}

// 区间和 [l, r]
long rangeSum(int l, int r) {
    return prefixSum(r) - prefixSum(l - 1);
}

两个循环的终止条件必须写对:add 的循环条件为 i <= n(越界即停止),prefixSum 的条件为 i > 0(i 变为 0 即停止)。把 add 写成 i < n 会漏掉最后一个区间;把 prefixSum 写成 i >= 0 会在 c[0] = 0 时恰好终止、看似正确,但一旦 c[0] 被误用就会出错。

建树可以逐个 add 完成,代价 O(n log n);更快的做法是先把原数组复制进 c,再对每个位置做 c[i] += c[i - lowbit(i)],代价 O(n)。

2.3 区间更新与单点查询的差分实现

把树状数组维护的对象换成差分数组,即可支持区间加、单点查:

// 内部维护差分数组 d

// 区间加:[l, r] 全部加 v
void rangeAdd(int l, int r, long v) {
    add(l, v);
    if (r + 1 <= n) {
        add(r + 1, -v);              // 右端点后一位抵消;越界时省略
    }
}

// 单点查询:a[i] 的值
long pointValue(int i) {
    return prefixSum(i);             // 差分的前缀和即原值
}

r + 1 > n 时不必执行第二次 add:超出数组范围的抵消项没有对应的元素。若把边界判断写错,会在最右侧区间的操作上产生 ±v 的累积误差,且只在查询接近 n 的位置时暴露。

2.4 区间更新与区间查询的双树状数组

按原理部分 3.4 节的推导,维护 d[j] 与 j · d[j] 两个数组:

class RangeFenwick {
    private final int n;
    private final Fenwick t1;        // 维护 d[j]
    private final Fenwick t2;        // 维护 j * d[j]

    RangeFenwick(int n) {
        this.n = n;
        this.t1 = new Fenwick(n);
        this.t2 = new Fenwick(n);
    }

    // 区间加:[l, r] 全部加 v
    void rangeAdd(int l, int r, long v) {
        t1.add(l, v);
        t2.add(l, v * l);
        if (r + 1 <= n) {
            t1.add(r + 1, -v);
            t2.add(r + 1, -v * (r + 1));
        }
    }

    // 前缀和:a[1] + ... + a[x]
    long prefixSum(int x) {
        return t1.prefixSum(x) * (x + 1) - t2.prefixSum(x);
    }

    // 区间和 [l, r]
    long rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

两处易错点:t2 中存放的是 j * d[j],因此每次更新都要乘上对应的下标(l 与 r + 1);prefixSum 的公式中 (x + 1) 乘的是 t1 的前缀和、减号后是 t2 的前缀和,两项写反会得到错误结果。推导方式见原理部分 3.4 节,可直接按公式核对。

3. 并查集实现要点

3.1 父数组与秩数组

class DSU {
    private final int[] parent;
    private final int[] rank;        // 树高的上界;若改用按大小合并则记录集合元素数
    private int count;               // 当前集合个数

    DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;           // 初始时每个元素自成一个集合,自己是根
        }
    }
}

初始化的要点是每个元素的 parent 指向自身,而不是 0。若把 parent 默认初始化为 0,则所有元素的根都是 0,全部被误判为同一集合,且不会有任何报错。

另一种常见写法是把根节点的 parent[x] 设为 x 以外的哨兵(如 −1),用 parent[x] < 0 判定根并顺便保存集合大小。这种写法把两个数组合并成一个,但可读性下降,且要求父指针与「规模」共用同一字段,需明确符号含义。

3.2 路径压缩的递归与迭代写法

递归写法最简洁:

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);     // 回溯时把 x 直接接到根
    }
    return parent[x];
}

递归的栈溢出风险:递归深度等于从 x 到根的路径长度。若未做按秩合并,且合并顺序恰好构造出长链(例如始终把大的集合挂到小集合下,或按 1 → 2 → 3 → … 的顺序合并),路径长度可达 O(n),递归深度同样为 O(n)。Java 的线程栈默认容量有限,深链上的 find 可能抛出 StackOverflowError;Python 的默认递归深度上限约 1000,更容易触发。两类触发条件都必须避免:使用按秩(或按大小)合并把路径长度限制在 O(log n),或以迭代方式实现压缩。

迭代写法用两趟循环:第一趟找根,第二趟改指针。

// 迭代式路径压缩:先把路径记录下来,再统一指向根
int find(int x) {
    int root = x;
    while (parent[root] != root) {       // 第一趟:找到根
        root = parent[root];
    }
    while (parent[x] != root) {          // 第二趟:把沿途节点直接连到根
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

第二趟必须先保存 parent[x] 再覆盖,写成先覆盖后取用会导致指针丢失并可能形成环(死循环)。若不需要完整压缩,也可以只做「路径减半」(parent[x] = parent[parent[x]]),同样能把后续查找代价控制在很低的水平,代码更短。

3.3 合并方向的优化

boolean union(int a, int b) {
    int ra = find(a);
    int rb = find(b);
    if (ra == rb) {
        return false;                    // 已在同一集合,无变化
    }
    if (rank[ra] < rank[rb]) {           // 保证 ra 是秩较大的一方
        int t = ra;
        ra = rb;
        rb = t;
    }
    parent[rb] = ra;                     // 把秩较小的树挂到较大的树上
    if (rank[ra] == rank[rb]) {
        rank[ra]++;                      // 两棵树等高时,合并后高度加一
    }
    count--;
    return true;
}

三处细节:

秩相等时才加一:只有「等高的两棵树合并」才会让新树高度增加
    写成每次合并都加一,会让秩增长过快,失去「树高上界」的含义

返回值语义:返回是否发生了合并
    调用方据此判断「这条边是否为有效连接」,是 Kruskal 等算法的基础

收集全部元素:需要枚举某集合的成员时,重新对每个元素 find 一次并按根分组
    不要在并查集内部维护成员列表,那会破坏按秩合并的表示不变性

若改用按大小合并,把 rank 换成 size,合并时 size[ra] += size[rb],并在需要时读取 size[find(x)] 得到集合规模。

3.4 带权并查集的权值维护与合并公式

约定 val[x] = val[parent[x]] + w[x],根的 w 恒为 0。find 后 w[x] 表示「x 相对根的偏移」。

find 的权值更新:

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    int root = find(parent[x]);          // 递归后 parent[x] 已指向根,w[parent[x]] 已是「旧父到根」的偏移
    w[x] += w[parent[x]];                // 由「x 到旧父」+「旧父到根」得到「x 到根」
    parent[x] = root;
    return root;
}

顺序不能颠倒:必须在覆盖 parent[x] 之前读取 w[parent[x]],否则读到的还是旧父作为父节点时的权值。

合并的权值推导。设待合并的约束为 val[y] − val[x] = delta。find 之后有 w[x] = val[x] − val[rx]、w[y] = val[y] − val[ry],其中 rx、ry 是两个根。要把 ry 挂到 rx 下,需要求出 w[ry] = val[ry] − val[rx]:

val[y] − val[x] = delta
(val[ry] + w[y]) − (val[rx] + w[x]) = delta
val[ry] − val[rx] = delta + w[x] − w[y]

即 w[ry] = delta + w[x] − w[y]
boolean union(int x, int y, int delta) {   // 约束为 val[y] − val[x] = delta
    int rx = find(x);
    int ry = find(y);
    if (rx == ry) {
        return w[y] - w[x] == delta;       // 已在同一集合:校验既有关系是否与约束一致
    }
    if (rank[rx] < rank[ry]) {             // 需要把 rx 挂到 ry 下,交换角色并反转约束
        int t = rx; rx = ry; ry = t;
        t = x;  x = y;  y = t;
        delta = -delta;
    }
    parent[ry] = rx;
    w[ry] = delta + w[x] - w[y];           // 由上述推导得出
    if (rank[rx] == rank[ry]) {
        rank[rx]++;
    }
    return true;
}

交换角色时必须同步反转 delta,否则新根之间的偏移方向与约束相反,后续所有查询都会偏移一个符号。带权并查集的调试建议是把 w 的实际含义(谁相对谁、正方向如何)写在代码注释中,这类实现的错误几乎全部来自方向约定不一致。

4. 复杂度与实测

4.1 操作复杂度表

结构 建树 / 预处理 点更新 区间更新 区间查询 单点查询 空间
前缀和 O(n) O(n) O(n) O(1) O(1) O(n)
差分数组 O(n) O(n) O(1) O(n) O(n) O(n)
稀疏表 O(n log n) 不支持 不支持 O(1) O(1) O(n log n)
树状数组(点更新) O(n) O(log n) — O(log n) O(log n) O(n)
树状数组(差分) O(n) — O(log n) — O(log n) O(n)
树状数组(双数组) O(n) — O(log n) O(log n) — O(n)
线段树(递归,带懒标记) O(n) O(log n) O(log n) O(log n) O(log n) O(4n)
线段树(迭代,无懒标记) O(n) O(log n) 受限 O(log n) O(log n) O(2·2^⌈log₂n⌉)
并查集(仅路径压缩) O(n) — — 摊还 O(log n) — O(n)
并查集(仅按秩合并) O(n) — — O(log n) — O(n)
并查集(两种优化) O(n) — — 摊还 O(α(n)) — O(n)

关于表中的口径需要说明三点:

线段树的建树是 O(n) 而非 O(n log n)
    节点总数为 O(n),每个节点只做一次常数级的合并

并查集的查询代价是摊还而非最坏
    首次遇到长链的那一次 find 仍可能需要遍历整条链

树状数组的 O(log n) 循环次数等于下标的二进制位数
    实际约等于 ⌈log₂n⌉,与线段树的树高同量级但常数更小

4.2 常数差异与实测方法

复杂度只给出量级,同一量级下的实际差距需要实测。三个可预期的差异来源:

递归与迭代
    线段树递归版每次操作有函数调用开销与栈帧管理,
    在 O(log n) 的循环体里被放大;迭代版把这两项换成数组下标运算

树状数组与线段树
    同为 O(log n),树状数组的循环体只有加法与下标跳转、无分支,
    线段树的循环体包含边界判断、pushdown、pushup 与函数调用

路径压缩的顺序敏感性
    并查集的实测耗时强烈依赖「合并与查询的交替模式」,
    先合并完全部关系再统一查询,与边合并边查询,代价差异明显

实测需要注意的事项:

规模至少覆盖三个量级(如 n = 10^3、10^5、10^7),观察曲线形态而非单点数值
区分随机输入与最坏输入:
    线段树的最坏输入是「查询区间几乎覆盖整棵树但又不完全覆盖」的端点选择;
    并查集的最坏输入是「按构造出的长链顺序访问」
预热与稳态:JVM 上的实现需要预热到即时编译进入稳态后再采集
同时记录分配量:树状数组与线段树的空间差异(O(n) 与 O(4n))会在内存与回收上体现

与 ArrayList、HashMap、TreeMap 这类容器不同,各语言标准库普遍不提供区间树或并查集的内置实现(其容器实现的复杂度承诺见 Java 集合框架实现原理),因此这三类结构通常需要按上述要点自行实现。微基准的设计方式、预热与测量轮次分离、黑洞消费结果、分叉隔离与结果判读见 JMH 微基准测试;量级结论与实测结论的分工见 复杂度与算法分析。

5. 工程应用

5.1 统计与报表中的区间聚合

按时间分桶的指标数据天然构成一个数组,报表需求是「任意时间段的汇总值」。若数据只追加不改写,用前缀和即可把查询降到 O(1);若历史数据会被回溯修正(迟到的数据补写、异常值更正),前缀和会整体失效,此时应在时间分桶上建立线段树或树状数组。

按天分桶的订单量数组 a[1..n]
    查询任意日期区间的订单总量        → 区间和
    查询任意日期区间的峰值日订单量    → 区间最值(不可逆,需线段树)
    修正某一天的数值                  → 点更新

进一步的需求「区间内最长连续达标天数」需要线段树维护前缀、后缀与整体最优(见原理 2.6 节)

选择依据回到原理第 1 节的分类:能否接受预处理整体失效,决定了是否可以用前缀和。

5.2 监控指标的滑动窗口统计

流式监控系统需要在一个固定长度的时间窗口上持续回答「最近 N 秒的和、最大值、平均值」。窗口滑动时进入一个新采样点、离开一个旧采样点,本质上是一次区间更新加一次区间查询。

窗口大小固定为 W,数据点按时间到达
    每个新点:把该时间桶的值更新,同时清除过期桶
    每次查询:对当前窗口对应的下标区间做区间聚合

若窗口内需要「最大值」:线段树维护区间最值
若窗口内只需要「总和」:树状数组即可
若窗口长度固定且只追加、按序过期:也可以用一个单调队列维护最值,
    代价 O(1) 摊还,比线段树更轻(见 [堆与优先队列](./heap_and_priority_queue.html) 的滑动窗口部分)

这一场景说明结构选型要考虑访问模式是否比通用区间操作更窄:当窗口只按时间顺序滑动、不含任意位置查询时,单调队列这类专用结构往往比通用线段树更合适。

5.3 等价类合并与数据治理

数据治理中的实体归并、重复检测、主数据对齐,本质都是把「判定为同一实体的记录」合并成等价类,并随时校验是否存在冲突。

账号归并
    同一自然人的多个账号由若干条匹配规则判定(同一手机号、同一证件号、同一设备)
    每条规则是一对「这两个账号等价」的事实 → union
    冲突检测:若存在「必定不等价」的约束(如同一证件号下不允许出现两个主体),
              在合并完成后逐条校验,见原理 6.4 节

重复检测与去重
    把可能重复的记录两两比较产生候选对,用并查集把候选对合并成簇
    统计簇的数量即去重后的记录数,簇的大小即重复次数

跨表主键映射
    多源数据的主键需要对齐,每条映射关系是一次 union,
    查询两个来源的主键是否指向同一实体即 find 比较

这一模式与数据治理流程的衔接见 mysql: 表结构变更与运维治理 的日常治理部分,其中关于分批数据处理与变更评估的做法同样适用于大批量关系的增量合并。

5.4 网络与集群的连通性判定

基础设施层面的连通性判定与并查集描述的是同一个问题:若干主机、容器或网络设备之间存在可达关系,需要判定任意两台是否互通、或网络被划分为几个连通域。

已建立的连接、路由可达关系、安全组放通规则都对应「两个节点相连」的事实
    union 合并后,find 相同 ⟺ 双向可达
    连通域个数 = 不同根的个数,可用于评估网络被分割成几段

防火墙规则的冲突检测与等价类问题同构:
    若两条规则声明了「这两个网段必须隔离」,
    而连通性事实又推出二者可达,即为冲突

需要注意并查集只支持合并:链路断开(删除一条边)无法通过基本并查集回退。若需要动态增删的连通性判定,必须改用其他结构,或按时间分片重建。

5.5 图算法中的辅助结构

并查集与优先队列是图算法中最常见的两个辅助结构,承担的角色不同。

Kruskal 最小生成树:并查集判定「加入这条边是否会成环」
    按权值从小到大扫描边,两端不在同一集合时采纳该边并合并
    代价 O(m log m)(排序) + O(m · α(n))(并查集)

并查集在 Kruskal 中的作用是替代「每次判断两端是否已通过已有边连通」的图搜索,
    把判定降到摊还近常数,这是 Kruskal 能在 O(m log m) 内完成的关键

Dijkstra 与 Prim:优先队列取出当前距离最小的未确定顶点
    堆的操作代价 O(log n),与线段树的量级相同但用途不同
    相关取舍见 [堆与优先队列](./heap_and_priority_queue.html)
// Kruskal:并查集判定成环,返回最小生成树权值,图不连通时返回 -1
int kruskal(int n, int[][] edges) {          // edges[i] = {u, v, w}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    DSU dsu = new DSU(n);
    int total = 0;
    int used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) {         // 两端不在同一集合,采纳这条边
            total += e[2];
            if (++used == n - 1) {
                break;                       // 已选够 n − 1 条边
            }
        }
    }
    return used == n - 1 ? total : -1;
}

生成树之外,并查集还大量出现在「按边权阈值统计连通性」「离线处理动态连通性查询」「按顺序加入元素并实时报告连通块数」等场景中,共同特征是只增不删的连通关系维护。Kruskal 与 Prim 的割性质、环性质、复杂度对照与稠密稀疏的选择依据见 最短路径与最小生成树。

6. 常见问题与排查

6.1 懒标记下推遗漏导致结果错误

现象:含区间更新的操作序列中,部分查询结果偏小或偏大;单独测试点更新与区间查询时结果正确,只在区间更新之后出错;错误的量值与更新涉及的区间长度相关。

原因:

在递归进入子节点之前没有调用 pushDown
    子节点在计算时看不到祖先的累积修改,读到的是旧值

在查询路径上没有调用 pushDown
    查询路径经过的节点可能只有祖先的标记而未更新自身

pushDown 中修改了子节点的值却未清除父节点的标记
    同一次修改被重复应用,结果偏大(且误差随访问次数累积)

标记的复合方式错误
    加法标记与赋值标记叠加时未清空旧标记,下推时把已被覆盖的修改又加了一次

排查:

1. 构造只含区间更新与区间查询、不含点更新的最小用例
      例如反复对 [1, n/2] 加 1,再查询 [1, n/4]
2. 用朴素实现(直接遍历区间修改)作为对照,逐次比对每一步的查询结果
3. 断言不变量:对任意节点,tree 应等于两个子节点 tree 之和(区间和场景)
      若该等式在更新后不成立,说明 pushUp 遗漏或顺序错误
4. 把根节点标记在每次操作后断言为空
      根节点的标记若未被下推,说明 pushDown 未在根上生效

防护:把 pushDown 统一放在「进入子节点之前」这一固定位置,并在所有需要进入子节点的分支上调用;查询与更新共用同一段下推逻辑,避免两处实现出现差异。

6.2 数组大小不足导致越界

现象:ArrayIndexOutOfBoundsException,下标略大于 2n 而小于 4n;或在小规模测试中正常、规模稍大即越界。

原因:

线段树容量按 2n 开辟
    n 不是 2 的幂时,树底参差,最深叶子的编号可接近 4n

上限计算取 4n 而非 4n + 1
    节点编号恰好取到 4n 时越界一格

树状数组容量按 n 开辟
    c 的下标范围是 1..n,需要 n + 1 个槽位

lowbit 相关循环的边界写成 i < n
    add 在 i 恰好等于 n 时仍需更新 c[n]

排查:打印构造过程中出现的最大节点编号,与容量比较;对 n 取 2^k − 1、2^k、2^k + 1(如 7、8、9)三组规模分别测试,这三种规模分别覆盖了树形的三类边界。

防护:线段树统一取 4 * n + 1,或改用补齐到 2 的幂的迭代形式(容量 2 * size);树状数组统一取 n + 1。

6.3 递归深度过大导致栈溢出

现象:StackOverflowError(Java)或 RecursionError(Python);崩溃前无异常输出;堆栈中同一方法名重复出现上千层。

原因:

线段树递归深度等于树高,为 O(log n),一般不会溢出
    但若区间划分写错(如 mid 取法导致子区间未缩小),递归可能无法终止

并查集递归版 find 的深度等于从元素到根的路径长度
    未使用按秩合并时,路径长度可达 O(n),深链上的 find 直接溢出
    这是并查集实现中最主要的栈溢出来源

树状数组不涉及递归,不受此影响

排查与修复:

1. 检查堆栈中重复的方法名,确认是线段树的递归还是并查集的 find
2. 线段树:核对 mid 的取法与子区间划分,确认每层区间严格缩小
3. 并查集:改用迭代式 find;或引入按秩(按大小)合并把路径长度限制在 O(log n)
4. 提高递归上限(Python 的 setrecursionlimit)只能推迟崩溃点,不解决问题的根源

6.4 并查集未压缩导致退化

现象:功能正确,但元素规模增大后耗时急剧增长;压测中单次操作耗时随元素数上升;偶发的长尾延迟明显。

原因:

既未做路径压缩、也未做按秩合并
    合并顺序是唯一决定树形的因素,长链可使单次 find 达到 O(n)

只做了路径压缩但没有按秩合并,且合并顺序特殊
    摊还代价为 O(log n),但仍高于两种优化同时使用的 O(α(n))

把路径压缩写成「压缩一半路径」
    后续查找仍需多层上溯,常数高于完整压缩

排查:

1. 统计所有元素到根的平均路径长度(对每个元素 find 一次并计数上溯步数)
       正常值应在个位数以内;若达到数十甚至上百,说明结构已经退化
2. 统计最大路径长度,确认树高是否超出 O(log n)
3. 检查 union 是否真的按秩或按大小选择根,而不是固定把后一个挂到前一个

防护:find 与 union 成对使用,路径压缩写在 find 中、按秩合并写在 union 中,两者缺一不可;在测试中断言树高不超过 2·⌈log₂n⌉。

6.5 离散化后未映射回原值

现象:输出结果总是比预期小若干倍;区间长度、坐标值、距离出现整型范围内的「合理但错误」的数值;对拍时与朴素实现差异随值域增大而增大。

原因:

输出时直接使用了离散化后的排名,而不是原坐标
    例如把坐标 10^9 输出为排名 3

区间长度按排名之差计算
    原坐标差为 10^9 + 7 − 10^9 = 7,排名差为 1,两者完全不同

离散化时只收集了「元素坐标」,没有收集查询区间的端点
    查询端点无法定位到排名,被迫取整或截断

去重不彻底
    排序后未去除相邻重复项,排名中夹杂空位,二分定位到的下标与预期不符

排查与防护:

1. 保留一份「排名 → 原值」的反查数组,任何对外输出都通过它还原
2. 单元测试中比较离散化前后的行为:用一组小值域的随机用例,
   同时跑离散化实现与直接实现,结果必须完全一致
3. 离散化集合中显式包含所有会被查询的端点坐标
4. 去重采用「排序后取与前一项不同的元素」的标准写法,并断言去重后规模等于不同坐标数

6.6 区间边界开闭混淆

现象:结果恒差一个元素或一个区间的量;边界位置(区间端点、中点)的更新或查询被漏掉;小规模用例偶然通过、大规模偶发不符。

原因:

维护端与查询端的口径不一致
    树状数组按闭区间 [l, r] 传参,但 rangeSum 内部按 r − 1 计算前缀

中点归属写反
    左子区间应为 [l, mid]、右子区间为 [mid+1, r]
    写成 [l, mid − 1] 与 [mid, r] 会丢失或重复中点

递归判断写成严格不等号
    ql <= mid 写成 ql < mid,恰好落在中点的区间不被访问

迭代线段树的半开区间约定与外部接口混淆
    query(l, r) 内部按 [l, r) 解释,调用方按 [l, r] 传参

并查集与区间无关,不受影响;差分数组的 r + 1 越界判断属于同类问题

排查与防护:

1. 把区间口径写进函数注释:闭区间记作 [l, r],半开区间记作 [l, r)
2. 所有涉及区间的用例必须覆盖三类边界:
       单个元素的区间(l == r)
       跨越中点的区间
       整个数组的区间(l == 1,r == n)
3. 用「逐一枚举全部区间并与朴素结果对拍」的方式测试小规模数组,
   可以一次性暴露全部边界错误
4. 接口层面统一口径,内部换算集中在一处,不要在多处重复 −1 或 +1

7. 检查清单

结构定义与容量:

- 线段树容量是否不小于 4n(或按补齐到 2 的幂的迭代方案取 2 * size)
- 树状数组容量是否为 n + 1,下标是否从 1 开始,c[0] 是否未被使用
- 并查集的 parent 是否初始化为 parent[i] = i,而不是 0 或 −1
- 离散化集合是否包含了全部将被查询的坐标,去重是否彻底
- 排名与原值的双向映射是否都已提供,对外输出是否统一走原值

区间口径与下标:

- 区间是闭区间还是半开区间,是否在接口注释与实现中一致
- 中点取法是否为 (l + r) / 2,左右子区间是否为 [l, mid] 与 [mid+1, r]
- 递归判断是否为 ql <= mid 与 qr > mid,而非严格不等号
- 线段树节点编号是否从 1 开始,子节点是否为 node * 2 与 node * 2 + 1
- 树状数组的更新循环条件为 i <= n、查询循环条件为 i > 0
- 差分实现中 r + 1 越界时是否已跳过第二次更新

线段树与懒标记:

- 是否在递归进入子节点之前调用 pushDown(查询路径同样需要)
- pushDown 是否先更新子节点的值、再清除父节点的标记
- 递归返回后是否调用 pushUp 重新合并
- 各类标记的复合方式是否明确,赋值类标记是否覆盖了旧的加法标记
- 空区间的单位元是否与合并运算匹配(加法用 0、最值用 ±∞)
- 合并信息是否是最小充分集:跨区间的答案所需的字段是否都已维护

树状数组:

- lowbit 实现是否为 x & (-x),是否只用于非负整数
- 点更新与前缀查询的循环方向是否相反且终止条件正确
- 区间和是否通过两次前缀相减得到,边界 l − 1 是否会取到 0
- 差分与双数组两种变体的下标乘数是否与该数组的含义一致
- 是否确认了所维护的运算可逆;不可逆运算是否已改用线段树

并查集:

- find 是否做了路径压缩,且压缩时未丢失父指针(迭代写法先取后改)
- union 是否按秩或按大小选择根,秩相等时是否只加一次
- 递归版 find 是否评估过路径长度,是否存在未做按秩合并导致的深链
- 带权并查集的权值含义与正方向是否已写成注释,交换角色时是否反转了约束
- 合并与查询的顺序是否满足问题要求(先合并全部相等约束、再校验不等约束)
- 需要枚举集合成员时是否通过重新 find 分组,而不是在并查集内部维护成员列表

测试与验证:

- 是否用小规模数组对拍:逐一枚举全部区间,与朴素实现比较
- 边界用例是否覆盖:单元素区间、跨中点区间、整个数组、单点更新、边界点更新
- 规模用例是否覆盖 n = 2^k − 1、2^k、2^k + 1 三类树形
- 并查集是否断言过树高上界与最终集合个数
- 离散化实现是否与小值域的直接实现做过一致性对拍
- 实测是否记录了规模、数据分布、版本与硬件等条件

四、总结

线段树与并查集分别对应两类需求:区间上的汇总信息维护,以及元素间等价关系的维护。两者共享同一个思路——用附加结构记录已经被压缩过的信息,使重复操作不再从原始数据重新计算。前缀和与差分只能覆盖「频繁查询」或「频繁更新」中的一侧,且依赖运算可逆;线段树与树状数组通过引入高度为 O(log n) 的附加结构,把两类操作的代价同时压到对数级;并查集通过把集合组织成以根为代表元的森林,把连通性判定压到摊还近常数。

结构层面:

- 区间问题的分类由三个维度决定:静态与动态、点更新与区间更新、合并运算是否满足结合律与是否可逆
- 满足结合律是能被区间合并的前提;可逆则决定能否用「前缀相减」代替「区间合并」
  区间和可逆,树状数组即可支持任意区间;区间最值不可逆,必须用线段树(静态时可用稀疏表)
- 稀疏表是纯静态结构的典型:O(n log n) 预处理换 O(1) 查询,前提是运算可重复贡献(幂等)

线段树层面:

- 线段树以区间为节点、二分构造,任意区间可拆成 O(log n) 个节点的并,
  任意单点修改只影响一条根到叶的路径,两个性质共同给出 O(log n) 的更新与查询
- 数组容量取 4n 是为了覆盖「n 不是 2 的幂时最深叶子编号可能接近 4n」这一最坏情形,
  实际节点数仍为 O(n);补齐到 2 的幂的迭代形式可用 2 * 2^⌈log₂n⌉
- 懒标记把区间修改记在完全覆盖的节点上,含义是「本节点值已更新、子节点尚未更新」;
  下推时机固定为「进入子节点之前」,顺序为「先下推、再递归」,返回时再 pushUp
- 标记的复合方式由运算决定:加法可叠加,赋值会覆盖旧的加法标记,两者不可交换
- 离散化把值域降为元素个数,但端点必须一并纳入,且对外输出必须映射回原值
- 合并信息按「父节点能否由子节点唯一推出」设计;答案跨区间时须额外维护前缀与后缀量

树状数组与并查集层面:

- 树状数组的二进制拆分把前缀分解为 O(log n) 个长度为 lowbit 的区间,
  更新沿 i += lowbit(i) 上行、查询沿 i −= lowbit(i) 下行
- 树状数组是线段树在「运算可逆且合并信息简单」时的紧凑实现:常数更小、代码更短;
  运算不可逆或信息复杂时必须换成线段树
- 差分技巧把区间加转化为两个点更新;维护 d[j] 与 j·d[j] 两个数组后,
  区间加与区间求和也可由树状数组完成
- 并查集把等价关系表示为一棵有根树,同集合等价于同根;
  路径压缩降低「被查找过的路径」的高度,按秩合并限制整体树高
- 两种优化同时使用时 n 次操作总代价为 O(n·α(n)),摊还每次 O(α(n));
  α 在一切可想象的规模下不超过 4,但严格结论是「近乎常数」而非常数,
  且该结论依赖结构不变量,引入撤销能力后不再成立
- 带权并查集用权值表示与父节点的关系量,压缩时累加、合并时按方向解出新根间的权值;
  种类并查集可用扩展域或带权两种方式实现

工程层面的三条判断:

- 选型按固定的四步顺序推进:能否接受预计算整体失效 → 是否只有区间更新 →
  运算是否可逆且信息是否简单 → 是否属于等价关系维护。
  能用树状数组时不应引入线段树,多出的复杂度没有换来任何能力
- 懒标记、数组容量、区间口径是线段树类实现中三个最常见的出错点,
  它们都不会立即报错,只在特定输入下产生偏一个元素或偏一段的结果,
  因此「小规模全面对拍 + 边界用例」是这类实现必须保留的验证手段
- 并查集的代价由「合并与查询的交替模式」决定,
  路径压缩与按秩合并必须成对使用;只增不删是并查集的适用边界,
  需要动态增删连通性时应改用其他结构

并查集在图中承担的连通性判定角色,与图的遍历算法关注的对象不同:前者回答「是否同属一个集合」,后者回答「集合具体由哪些顶点与边构成」,两者在最小生成树与连通分量统计中常配合使用。区间聚合与离散化的处理方式在报表与监控统计中反复出现;等价类合并与冲突检测的做法与数据治理中的实体归并一致,相关流程见 mysql: 表结构变更与运维治理。摊还分析的三种论证方法、复杂度结论的适用边界与实测方法,见 复杂度与算法分析 与 JMH 微基准测试;树状数组与线段树所依托的完全二叉树数组表示、区间合并与分治结构,与 二叉树与二叉搜索树 中的下标算术部分同源。