序列并查集的线性算法

  • 2021 年 1 月 31 日
  • 筆記

本文提供了序列上并查集的线性合并与查询的算法及其 C++ 实现。一种更具有普适性但实现细节与此不同的树上线性并查集算法见参考文献[1,3]，其中 Tarjan 的论文[3] 中包含处理动态加点的树上并查集问题的方法。

Introduction

序列上的并查集问题可以描述为：

1.初始序列上有 \(n\) 个元素，各自为一个元素段。
2.进行 \(m\) 次操作与询问。

  • 将两个相邻的元素段合并。
  • 查询某个元素所在的段。

直接使用传统的并查集做法，时间复杂度为 \(O(m\alpha(m+n,n)+n)\)，空间复杂度为 \(O(n)\) [3]。

其中 \(\alpha\) 函数是我们熟知的 Ackermann 函数的反函数。

具体地 \(\alpha(m,n)=\min\{i>1|\mathop{Ackermann}(i,\lfloor\frac{m}{n}\rfloor)>\log_2 n\}\) [4]。

下文将提供一种时间复杂度为 \(O(n+m)\)，空间复杂度为 \(O(n/\log n )\) 的算法解决这个问题。

Algorithm

考虑将序列分块，每块的大小为 \(b\)，不妨认为 \(b<w\)，其中 w 为计算机的字长。

然后将每块左端的元素提出来，用传统并查集维护，这部分的时间是 \(O(\frac{m}{b}\alpha(n+m,n)+n)\)。

然后每块用一个整数存储块内的状态，其中整数二进制的第 \(i\) 位表示块内从右往左数第 \(i\) 号元素是否向左合并过，其中 0 表示合并过，1 表示没有。

考虑合并两段的操作，先找到右侧合并段最左侧元素对应在块内对应的位，将其从 1 赋位 0。之后，如果该元素位于块内最左端则将该块合并合并到前一块上。

考虑查询某元素所在的段，先查询该元素块内其自身与左侧第一个 \(1\) 的位置，这部分可以用先按位右移去除右侧元素的干扰，然后 lowbit 找出第一个 1 的位置。如果存在 1，则该元素所在段的最左端即为块内所查到的 1 的位置。否则，查询该块并查集的 root 块，再查询 root 块的 lowbit 即可。

单次合并查询操作的非并查集部分的时间复杂度是 \(O(1)\)。

当 \(b\) 取 \(\log_2 n\) 时，总时间复杂度为 \(O(n+m)\)，空间复杂度为 \(O(n/\log n)\)。

特别地，并查集只使用路径压缩优化而未按秩合并复杂度依然是 \(O(n+m)\)，因为这样子并查集部分的时间复杂度为 \(O(m \log_{1+m/n}{n})\) [2]。

c++ 实现 :

const int N = 1000000;

int lowbit( int x ) {             // 二进制下最低位
	return x & -x;
}

namespace LinearSequenceDisjointSet {
	
	const int MaxN = N;           // 最大的 n 值
	const int BlkL = log2(N);     // 块长
	
	const int Mask = ( 1 << BlkL ) - 1; 
	
	int pre[ MaxN / BlkL ];       // 并查集数组
	int dat[ MaxN / BlkL ];       // 块内信息
	
	void init() {
		for( int i = 0; i < MaxN / BlkL; i ++ ) {
			pre[i] = i;
			dat[i] = Mask;
		}
	}
	
	int findP( int x ) {          // 路径压缩并查集的查询操作
		if( x == pre[x] ) return x;
		return pre[x] = find( pre[x] );
	}
	
	int find( int x ) {           // 找到该段最左端的元素
		int b = x / BlkL;
		int p = x % BlkL;
		int s = b * BlkL;
		
		int m = dat[b] & ( Mask + 1 - (1 << p) );
		
		if( !m ) {
			s -= b - findP(b);
			m = dat[findP(b)];
		} 
		
		return s * BlkL + BlkL - log2( lowbit(m) ) - 1;
	}
	
	void join( int x ) {          // 将 x 元素与前一个位置合并
		int b = x / BlkL;
		int p = x % BlkL;
		
		p = BlkL - p - 1;
		
		dat[b] &= ( Mask - (1 << p) );
		
		if( p == BlkL - 1 and b ) {
			pre[ findP(b) ] = findP(b - 1);
		}
	}
	
}

Application

例题 : 有一个序列 \({a_n}\)，初始值输入，然后有 \(m\) 次操作，每次将一个前缀加上一个常数，并返回全局最大值。

考虑维护序列的单调栈，每个元素维护初始值与附加值，前缀加操作时找到单调栈内最右侧能被操作覆盖到的元素，并将其附加值加上操作的常数。

如果该元素的初始值与附加值的和大于其右侧元素的初始值，则弹出右侧元素。

我们发现单调栈内每个元素控制着以它为左端点的原序列上的一段，而弹出操作则需要合并相邻的两段，于是可以用分块序列并查集维护。

总时间复杂度 \(O(n+m)\)。

References

  1. ljt12138，RMQ标准算法和线性树上并查集
    //ljt12138.blog.uoj.ac/blog/4874
  2. wang3312362136，路径压缩优化并查集的时间复杂度
    //blog.csdn.net/wang3312362136/article/details/86475324
  3. H.N.Gabow & R.E.Tarjan，A Linear-Time Algorithm for a Special Case of Disjoint Set Union，JOURNAL OF COMPUTER AND SYSTEM SCIENCES 30, 209-221 (1985)
  4. inverse Ackermann function
    //xlinux.nist.gov/dads/HTML/inverseAckermann.html

VirMach 便宜 VPS

QNews

QNews