并查集：推导部分和

这篇具有很好参考价值的文章主要介绍了并查集：推导部分和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

推导部分和

问题描述

对于一个长度为 $N$ 的整数数列 $A_{1}, A_{2}, \cdots A_{N}$ , 小蓝想知道下标 $l$ 到 $r$ 的部分和 $\sum_{i=l}^{r}=A_{l}+A_{l+1}+\cdots+A_{r}$ 是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的 $M$ 个部分和的值。其中第 $i$ 个部分和是下标 $l_{i}$ 到 $r_{i}$ 的部分和 $\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}$ , 值是 $S_{i}$ 。

输入格式

第一行包含 3 个整数 $N 、 M$ 和 $Q$ 。分别代表数组长度、已知的部分和数量和询问的部分和数量。

接下来 $M$ 行, 每行包含 3 个整数 $l_{i}, r_{i}, S_{i}$ 。

接下来 $Q$ 行, 每行包含 2 个整数 $l$ 和 $r$ , 代表一个小蓝想知道的部分和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

样例输入

样例输出

15
6
UNKNOWN

评测用例规模与约定

对于 $\\%$ 的评测用例, $\leq N, M, Q \leq 10,-100 \leq S_{i} \leq 100$ 。

对于 $\\%$ 的评测用例, $\leq N, M, Q \leq 20,-1000 \leq S_{i} \leq 1000$ 。

对于 $\\%$ 的评测用例, $\leq N, M, Q \leq 50,-10000 \leq S_{i} \leq 10000$ 。

对于 $\\%$ 的评测用例, $\leq N, M, Q \leq 1000,-10^{6} \leq S_{i} \leq 10^{6}$ 。

对于 $\\%$ 的评测用例, $\leq N, M, Q \leq 10000,-10^{9} \leq S_{i} \leq 10^{9}$ 。

对于所有评测用例, $\leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N$ , $\leq l \leq r \leq N$ 。数据保证没有矛盾。

解题思路一加权并查集

灵光一闪：部分和+重复
（多次求部分和最快方法——前缀和）
给出指定区间 $[l, r]$ 的部分和，根据前缀和的思想，若下标 $l, r$ 处的前缀和分别为 $S_{l},S_{r}$ ,那么区间 $[l, r]$ 的部分和可表示为 $S_{r}-S_{l-1}$ .
问题：
不知道数组全貌，没办法求完整的前缀和
基本情况
给出指定区间 $[l, r]$ 的部分和，问我们区间 $[l, r]$ 的部分和
简单延申
给出指定区间 $[l, r]$ 和 $[r, r + k]$ 的部分和，问我们区间 $[l, r + k]$ 的部分和
发现
l指向r，r指向r+k，结果两两组合都可以求出来部分和——并查集

注意：由于部分和的值始终为编号较小的结点 $d i s [l]$ 与编号较大的结点 $d i s [r]$ 间的差值，因此对于一个结点 $i$ ,若其并查集祖宗结点 $j$ 的编号大于 $i$ ,那么 $d i s [i]$ 记录的距离为 $s$ ,否则，记录的是 $s$ 的负数。例如，结点 4 到 5 的距离为 6 ，那么结点 5 到结点 4 的距离为 -6 。
步骤：
1、初始化：需要将并查集数组有效部分的长度初始化为 $n + 1$ ,
2、合并：对于每个输入的区间端点 $l, r$ 和部分和 $s$ ，并查集结点 $l - 1$ 与 $r$ 之间的距离为 $s$ , 结点合并时，并查集的权数组 $d i s$ 维护 $s$ .
3、将所有的区间和进行并查集连通后，对输入的需要求解的区间和 $[ql, q r]$ 进行判断，如果 $ql, q r$ 有相同的祖宗结点，那么 $d i s [ql] - d i s [q r]$ 即为区间和。否则，说明 $ql, q r$ 并不连通，此时无法求出区间和。文章来源地址https://www.toymoban.com/news/detail-503924.html

AC Code(Python3)

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
N=int(1e5)+10

father=[0]*N
dis=[0]*N
def init(n:int):
    for i in range(1,n+1):
        father[i]=i
def find_father(x:int):
    if father[x]==x:return x
    t=father[x]   
    father[x]=find_father(father[x])
    dis[x]+=dis[t]                      #权重数组dis维护两个结点间的距离，此题为区间和
    return father[x]
def unite(x:int,y:int,w:int):
    fx=find_father(x); fy=find_father(y)
    if fx==fy:return
    father[fx]=fy
    dis[fx]=dis[y]-dis[x]+w         #合并时维护节点间的区间和(fx>fy则为负值，fx<fy则为正值)

if __name__=='__main__':
    n,m,q=map(int,input().split())
    init(n)                         #对加权并查集初始化
    for i in range(m):
        l,r,s=map(int,input().split())
        l-=1                        #类似前缀和，[l,r]的和为l-1到r的距离
        unite(l,r,s)                #合并结点l与r
    res=[]                          #存放结果的列表
    for i in range(q):
        ql,qr=map(int,input().split())
        ql-=1                       #与l情况相同
        faql=find_father(ql); faqr=find_father(qr)
        if(faql!=faqr):res.append("UNKNOWN")    #两个结点不连通，此时的和不可求解
        else:res.append(dis[ql]-dis[qr])  #部分和为两结点间dis的差值(由前缀和性质，部分和一定是左边区间减右边区间)
    for item in res:
        print(item)