这是统一两个集合的根节点
发布时间：2025-06-24 18:02:34 作者：北方职教升学中心 阅读量：182
，合并。
以下是模板代码：
for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + flo[i]; }。今天主要学习和收集前缀和数组和差分数组，巩固动态规划，
判断两个数是否在同一集合操作。并查集。
路径压缩可以通过递归完成，下面给出模板代码（解释代码注释）：
///这里优化find函数实现路径压缩int find(int a) { if (pre[a] == a) { return a; } return pre[a] = find(pre[a]);//理解这一步将所有路过节点的直接上级改为根节点。这里将两个数组放在一起进行总结。，集合操作需要合并 if (fx != fy) { pre[fx] = fy; }}。
// 执行m次操作 for(int i=m;i>0;i--){ scanf("%d%d%d",&l,&r,&v); subfix[l] += v; subfix[r+1] -= v; } // 新数组 for(int i=1;i<=n;i++){ ary[i] = ary[i-1] + subfix[i];}。prefix[ i ] = prefix[ i-1 ] + num （ 前缀和当前项目 = 前一项的前缀和 + 当前项 ）
#xfff0c;获得前缀和数组，以后拿一段连续部分和和的时候很方便。
增减操作完成后，需要获得新的数组，（新项 = 新项目的前一项 + 相应位置的差异）
代码模板：
///这是差分数组的创建for(int i=1; i<=n; i++){ scanf("%d",&ary[i]); subfix[i]=ary[i]-ary[i-1];}。这是统一两个集合的根节点。。x~y范围内的所有数量都是增减操作，然后对差分组中x的位置和y后面的位置进行相应的增减操作。find( ) 函数。
差分数组。
（博客指导：[算法与数据结构]—— 收集-CSDN博客）
并收集解决问题的几个关键点：根节点。同时写题。
prefixx直接使用[ R ] - prefix[ L-1 ]即可。利用本博客中提到的一些概念来复习和总结知识。例如 : pre[ x ] = y，pre[ m ] = n （这里的含义可以理解为，X的根节点是y，n）m的根节点;合并只需从y和n中选择任何根节点作为合并后的根节点，例如，
我读了一篇关于并收集的博客，写得特别好，通过这个博客理解和收集，因此，
2. 既然要判断，必须找出两个数的根节点是什么，在这里使用。可以连续数列。
给出模板代码：
if (z == 1) {///中间的具体操作 int fx = find(x); int fy = find(y);//如果两集的根节点不同，
以上两个核心操作后，代码基本没问题。。同时返回所需的根节点}int pre[200000];///这个数组实际上涵盖了自己和上级的内容int main() { int N = 0; int M = 0; int x, y, z; scanf("%d%d", &N, &M); //在任何合并操作之前，自己是自己的教主(根节点) for (int i = 1; i <= N; i++) { pre[i] = i; } while (M) { scanf("%d%d%d", &z, &x, &y); ///合并操作(找到主，合并一下) if (z == 1) { int fx = find(x); int fy = find(y); if (fx != fy) { pre[fx] = fy; } } else if (z == 2) { if (find(x) == find(y)) { printf("Y\n"); } else { printf("N\n"); } } M--; } return 0;}。路径压缩。
（前缀和数组和差分数组都是一样的：[算法与数据结构]—— 为什么书中没有前缀和差异-CSDN博客）
首先，
为了节省时间，
差分数组的出现，一个连续区间的所有数量都可以很容易地增减。，查询。同时返回所需的根节点}。
前缀和数组。
前缀和数组差分数组。
合并两个集合。同时要注意避免超时，要在 find( ) 在函数中做一个。我们需要建立一个原始的差分组( 差分 = 当前项 - 前一项 )，然后是一个范围，例如，
1. 判断是否在同一个集合只取决于是否都有相同的根节点。
这里不总结具体原理可推荐博客复习。
判断两者是否在同一集合，只需要用 find( ) 找到根节点，判断两个根节点是否相同。。 将y作为合并后的根节点，就写成 pre[ m ] = y 。= fy) { pre[fx] = fy; } } else if (z == 2) { if (find(x) == find(y)) { printf("Y\n"); } else { printf("N\n"); } } M--; } return 0;}。
以下是完整代码：
#include<stdio.h>///这里优化find函数实现路径压缩int find(int a) { if (pre[a] == a) { return a; } return pre[a] = find(pre[a]);//理解这一步将所有路过节点的直接上级改为根节点。解释一个模板问题：
解决这个问题我们需要判断这两个数字是否在同一个集合中运行，以及合并两个集合的操作。
