数据结构：点分治学习笔记

饕子

652人浏览 · 2023-05-10 13:17:06

饕子 · 2023-05-10 13:17:06 发布

数据结构：点分治学习笔记

点分治（Point Divide and Conquer）是一种基于分治思想的算法，能够有效地解决与树相关的复杂问题。本文将为大家介绍点分治算法的基本概念、实现方法、时间复杂度和应用场景，并给出相应的示例代码。

1. 基本概念

点分治是一种利用树的结构进行分治的算法，其核心思想是：在树上选择一个重心（Centroid）节点，将原问题分解为若干个子问题（每个子问题都与当前重心有关），然后对每个子问题递归处理。这样做的好处是，可以大大缩小问题的规模，从而简化计算过程，提高效率。

2. 实现方法

点分治的实现方法可以分为三个步骤：

2.1 选择重心节点

为了满足点分治的要求，我们需要首先选择一棵树中的重心作为递归的起点。重心节点的定义如下：

对于一棵树 $T$ ，其重心节点为使得任意连通块中最大子树的节点数最小的节点；
对于无向图 $G$ ，其重心节点为使得删除该节点以后所得到的连通块中最大子图的节点数最小的节点。

选择重心节点的方法有多种，例如通过 DFS 遍历求出每个树的子树大小，然后选择子树大小最小的节点作为重心；或者通过类似二分的方式，逐步缩小重心的范围，最终选择剩余节点中的任意一个。在实践中，具体选择哪种方法，主要取决于问题的具体要求和数据规模。

2.2 分治处理

选择重心节点之后，我们需要对当前节点的所有儿子节点进行处理，并将原问题分解为若干个子问题。此时，我们可以采用与标准分治算法相同的递归方法，对每个子问题进行处理，最后再将答案合并起来，得到原问题的答案。

分治处理的具体实现方法与普通分治方法相似，但是需要注意：在处理每个子问题时，需要排除当前重心节点，否则会出现重复计算的情况。

2.3 合并子问题

在处理完所有子问题后，我们需要将它们的结果按照一定的方式合并起来，得到原问题的答案。这里所说的“合并”，并不仅仅是简单的加法和减法运算，而是需要对不同子问题之间的关联性进行分析，寻找它们之间的联系和差异。

在实际运用中，合并的方法有多种，例如将多个问题的结果进行求和、求最大值或者求最小值等等。此外，在一些特殊情况下，我们还可以通过优化合并过程，进一步提高算法的效率。

3. 时间复杂度

点分治算法的时间复杂度如下：

选择重心节点： $O (n)$ ；
分治处理： $O(nlog⁡n)O(n\log n)$ ；
合并子问题： $O(nlog⁡n)O(n\log n)$ 。

因此，点分治算法的总时间复杂度为 $O(n\log^2 n)$ （其中 $n$ 表示树的节点数），相对于暴力算法的 $O(n^2)$ 而言，有了明显的提升。

4. 应用场景

点分治算法的应用场景非常广泛，尤其适用于与树相关的问题。在本节中，我们以点分治算法在树链剖分中的应用为例，介绍其具体使用方法。树链剖分是一种常用的树上问题解法，能够有效地解决树上路径问题，例如树链求和、树链取最大值、树链修改等等。

4.1 树链剖分

树链剖分（Heavy-Light Decomposition）是一种利用重链和轻链将树上路径分解为若干条链的方法。其中，重链是指从儿子节点向下延伸较多的链，轻链则相反，从儿子节点向下延伸较少的链。树链剖分的核心思想是将原问题分解为若干个子问题，每个子问题对应一条链，然后逐条链进行处理、合并。

在实现树链剖分时，我们需要首先选择根节点，然后计算每个节点的子树大小、深度、父亲节点、重儿子节点等信息，最后对每条链进行编号，并记录链顶节点、链底节点和链上信息等内容。具体实现方法可以参考下面的代码示例：

def dfs(u, f):
    size[u], son[u], fa[u] = 1, 0, f
    for v in G[u]:
        if v != fa[u]:
            depth[v] = depth[u] + 1
            dfs(v, u)
            size[u] += size(v)
            if size[v] > size[son[u]]:
                son[u] = v

def dfs2(u, top):
    dep[u], id[u], tp[u] = depth[u], ++tot, top
    if not son[u]:
        return
    dfs2(son[u], top)
    for v in G[u]:
        if v != fa[u] and v != son[u]:
            dfs2(v, v)

def lca(u, v):
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        u = fa[tp[u]]
    return u if dep[u] < dep[v] else v

def query_path(u, v):
    ans = 0
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        ans += query(id[tp[u]], id[u])
        u = fa[tp[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    ans += query(id[u], id[v])  # 注意不要重复计算lca
    return ans

def modify_path(u, v, val):
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        modify(id[tp[u]], id[u], val)
        u = fa[tp[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    modify(id[u], id[v], val)  # 注意不要重复计算lca

dfs(1, 0)
dfs2(1, 1)

上述代码中，dfs 函数用于计算每个节点的子树大小、深度和父亲节点，以及重儿子节点。dfs2 函数用于计算每个节点的深度、所在链的编号和链顶节点。lca 函数用于计算两个节点的最近公共祖先。query_path 函数用于查询路径上数值的和，modify_path 函数用于修改路径上每个节点的值。

4.2 点分治实现

在使用点分治算法实现树链剖分时，我们可以首先选取根节点作为重心节点进行递归，处理完所有子问题后再将它们合并起来。具体代码如下：

INF = 0x3f3f3f3f

def solve(u):
    size[u], son[u] = 1, 0
    for v in G[u]:
        if v != fa[u] and not vis[v]:
            solve(v)
            size[u] += size[v]
            if size[v] > size[son[u]]:
                son[u] = v
    if max(size[son[u]], tot - size[u]) <= tot // 2:
        centroid.append(u)

def query_subtree(u, v):
    return query_path(u, v)

def modify_subtree(u, v, val):
    modify_path(u, v, val)

def dfs_centroid(u):
    vis[u] = True
    for v in G[u]:
        if vis[v]:
            continue
        dfs_centroid(v)

def solve_centroid(u):
    vis[u] = True
    for v in G[u]:
        if vis[v]:
            continue
        solve_subtree(v)
    for v in G[u]:
        if vis[v]:
            continue
        centroid.clear()
        tot = size[v]
        solve(v)
        for c in centroid:
            dfs_centroid(c)
        solve_centroid(c)

def solve_subtree(u):
    solve(u)
    vis[u] = True
    for v in G[u]:
        if vis[v]:
            continue
        solve_subtree(v)

solve_centroid(1)

上述代码中，solve 函数用于求解以当前节点 u 为重心的子树大小，并找到当前节点的重儿子。query_subtree 和 modify_subtree 分别用于查询和修改以当前节点为根节点的子树。dfs_centroid 函数用于遍历当前重心子树中的所有节点，并对其标记为已访问。solve_centroid 函数用于求解当前重心子树中的所有节点，并递归处理其它子树。solve_subtree 函数则用于处理单个子树。

在以上实现中，我们先通过 solve 函数求解以当前节点 u 为重心的子树大小和当前节点的重儿子；然后通过 solve_centroid 函数选取根节点，计算各个子树的重心节点，并递归处理每个子树；最后通过 solve_subtree 函数处理单个子树。

5. 示例代码

下面是一份基于 Python 语言的点分治算法代码，可以供大家参考学习：

# Python 3.7

import sys

sys.setrecursionlimit(100005)

maxn = 200005
logn = 20

G = [[] for _ in range(maxn)]

size = [0] * maxn
fa = [0] * logn * maxn
depth = [0] * maxn
vis = [False] * maxn

tot = 0
id = [0] * maxn
tp = [0] * maxn
dep = [0] * maxn

centroid = []

def dfs(u, f):
    size[u], fa[u] = 1, f
    for v in G[u]:
        if v != f:
            depth[v] = depth[u] + 1
            dfs(v, u)
            size[u] += size[v]

def dfs2(u, top):
    dep[u], id[u], tp[u] = depth[u], ++tot, top
    if not son[u]:
        return
    dfs2(son[u], top)
    for v in G[u]:
        if v != fa[u] and v != son[u]:
            dfs2(v, v)

def lca(u, v):
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        u = fa[tp[u]]
    return u if dep[u] < dep[v] else v

def query_path(u, v):
    ans = 0
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        ans += query(id[tp[u]], id[u])
        u = fa[tp[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    ans += query(id[u], id[v])  # 注意不要重复计算lca
    return ans

def modify_path(u, v, val):
    while tp[u] != tp[v]:
        if dep[tp[u]] < dep[tp[v]]:
            u, v = v, u
        modify(id[tp[u]], id[u], val)
        u = fa[tp[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    modify(id[u], id[v], val)  # 注意不要重复计算lca

def solve(u):
    size[u], son[u] = 1, 0
    for v in G[u]:
        if v != fa[u] and not vis[v]:
            solve(v)
            size[u] += size[v]
            if size[v] > size[son[u]]:
                son[u] = v
    if max(size[son[u]], tot - size[u]) <= tot // 2:
        centroid.append(u)

def solve_subtree(u):
    solve(u)
    vis[u] = True
    for v in G[u]:
        if vis[v]:
            continue
        solve_subtree(v)

dfs(1, 0)
dfs2(1, 1)

solve_subtree(1)

乐奇 Rokid 开放社区

更多推荐

微安级唤醒、2节干电池直供：CI3422如何重新定义电池供电设备的语音交互

乐奇 Rokid 开放社区

基于 AIUI 框架的眼镜端坐姿监测智能体：WorkerMonitor 设计与实现

基于AIUI框架，设计并实现眼镜端坐姿监测智能体WorkerMonitor。通过加速度传感器实时采集头部姿态数据，结合校准偏移量进行三态分类（正常/警示/异常），每秒采样一次，累计时长并低打扰提醒。每2小时调用LLM生成个性化健康建议，支持自动工作/休息切换与隐藏模式，兼顾隐私与体验。项目采用Ink单文件页面结构，实现极简交互与可持续反馈，为长期伏案者提供无感式颈椎健康管理方案。