ST表-用于优化RMQ问题

状态分析

因为一般指数都会向上取整，所以询问的时候都会把数组区间囊括

例题分析

代码复现

import math
def st_init(n,a):
    L = math.ceil(math.log2(n) + 1)
    #[i][j]表示区间[i,i+2^j-1]的最大值
    f = [[0]*L for i in range(n)]
    #边界
    for i in range(n):
        f[i][0] = a[i]
    #打表
    for j in range(1, L):
        pj = 1 <<(j - 1)
        for i in range(n-pj):
            f[i][j] = max(f[i][j - 1],f[i + pj][j - 1])
    return f
def query(f, l, r):
    s = int(math.log2(r-l+1))
    return max(f[l][s], f[r-(1<<s) + 1][s])

N,Q = map(int,input().split())
a = list(map(int,input().split()))
f = st_init(N,a)
for _ in range(Q):
    l, r = map(int,input().split())
    l, r = l-1, r-1
    print(query(f,l,r))

并查集

例题分析1

代码复现

#运用到路劲压缩
def Findroot(x):
    if x == p[x]:
        return x 
    p[x] = Findroot(p[x])
    return p[x]

def Merge(x, y):
    rootx, rooty = Findroot(x), Findroot(y)
    p[rootx] = rooty

def Query(x, y):
    #查询集合x, y是否属于同一个集合
    rootx,rooty = Findroot(x), Findroot(y)
    return rooty == rootx

n, m = map(int,input().split())
p = list(range(n+1))
for _ in range(m):
    op, x, y = map(int,input().split())
    if op == 1:
        Merge(x, y)
    else:
        if Query(x, y):
            print("YES")
        else:
            print("NO")

例题分析2

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。
现在，反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中)
输入描述
输入第一行包含两个整数n,m，分别表示星球的数目和以太隧道的数目。星球用0~n-1的整数编号。接下来的 m 行，每行包括两个整数 x,y，表示星球 x和星球 y之间有“以太”隧道，可以直接通讯。接下来的一行为一个整数 k，表示将遭受攻击的星球的数目。接下来的k行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这k个数互不相同，且都在 0到n-1的范围内。
其中,1≤m≤2x10’,1≤n≤2m，x≠y.

状态分析

代码复现

def Findroot(x):
    if x == p[x]:return x
    p[x] = Findroot(p[x])
    return p[x]

n,m = map(int,input().split())
p = list(range(n))

#邻接表存图
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int,input().split())
    g[x].append(y)
    g[y].append(x)
#所有被毁的点
destory = []
vis = [0] * n #标记是否被损毁
k = int(input())
for _ in range(k):
    x = int(input())
    destory.append(x)
    vis[x] = 1
res = n - k
for u in range(n):
    if vis[u]: continue
    for v in g[u]:
        if vis[v]:continue
        rootu, rootv = Findroot(u), Findroot(v)
        if rootu != rootv:
            p[rootu] = p[rootv]
            res -=1
ans = [res]
#逐步建边
for u in destory[::-1]:
    vis[u] = 0
    res +=1
    for v in g[u]:
        if vis[v]: continue
        rootu, rootv = Findroot(u), Findroot(v)
        if rootu != rootv:
            p[rootu] = p[rootv]
            res -= 1
    ans.append(res)
for x in ans[::-1]:
    print(x)

合并并查集的方法

启发式合并：按照子树的节点大小

按秩合并：按照子树的深度

可撤销并查集

可撤销并查集(Reversible Union-Find)是一种扩展了标准并査集(Union-Find)数据结构的数据结构，它允许在进行连接(Union)和查询(Find)操作的同时，能够回退(Undo)或者撤销之前的操作。这种数据结构通常用于支持一些需要回滚操作的应用，比如在离线算法中，或者需要进行回退的决策问题中。当然主要是应用于在线算法，因为离线算法反悔可以完全输入后在一起处理。

带权并查集

就是每一条边现在的权值都不是固定的

代码复现

def find(x):
    if f[x] == x:
        return x
    fa = find(f[x])
    dis[x] += dis[f[x]]
    f[x] = fa
    return f[x]

寻找函数的代码更改如下：

例题分析

思路分析

感悟

后面部分都是属于并查集的提升，结合了前缀和和路径的权重都是基于并查集的原理，有点难理解但是多做题就好了！

蓝桥杯云课学习笔记分享，欢迎大佬们批评指正！

一直在进步就好咯！

by 闻不多