Sqrt Decomposition

Resoures:

E-Maxx

Shafayet blog 

Rezwan's CP Blog  

Anudip blog 

Tanvir's Blog 

MO'S Algo 

One problem-solution discussion 2D SQRT 

MO’s Algorithm (Query square root decomposition)

Mo's algorithm (HackerEarth)

GeeksForGeeks

CF blog: 1 2

Cf blog3 

CF blog4

[Tutorial] Two ways to apply Mo's Algorithm on Trees 

Mo's Algorithm on Trees [Tutorial] 

Practice Problem

Practice Contest

  Youtube:

Rachit Jain 

Gaurav sen 

SolverToBe 

Santo vai video 

Implementation:

	#include<bits/stdc++.h>
	using namespace std;
	#define nx 10000
	int blk_sz;
	int ar[nx];
	int block[nx];
	///O(1)
	void update(int idx, int val)
	{
	int blockNumber = idx/blk_sz;
	block[blockNumber] += val - ar[idx];
	ar[idx] = val;
	}
	/// O(sqrt(n))
	int query(int l, int r)
	{
	int sum = 0;
	while(l < r && l%blk_sz != 0 && l != 0)
	{
	sum += ar[l];
	l++;
	}
	while(l+blk_sz <= r)
	{
	sum += block[l/blk_sz];
	l += blk_sz;
	}
	while(l <= r)
	{
	sum += ar[l];
	l++;
	}
	// cout << sum << " ";
	return sum;
	}
	void preprocess(int a[], int n)
	{
	int blk_idx = -1;
	blk_sz = sqrt(n);
	for(int i = 0; i < n; i++)
	{
	ar[i] = a[i];
	// cout << ar[i] << " ";
	if(i%blk_sz == 0)
	{
	blk_idx++;
	}
	block[blk_idx] += ar[i];
	// cout << block[blk_idx] <<" ";
	}
	// cout << endl;
	}
	/**
	10
	1 5 2 4 6 1 3 5 7 10
	**/
	int main()
	{
	freopen("in.txt", "r", stdin);
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cout << a[i] << " ";
	cout << endl;
	preprocess(a, n);
	cout << query(0,9)<<endl;
	cout << query(3,8)<<endl;
	cout << query(1,6)<<endl;
	update(8,0);
	cout << query(8,8)<<endl;
	return 0;
	}

view raw SquareRootDecomposition.cpp hosted with ❤ by GitHub

Implementation:

	/// Topic: LCA, O(sqrt(height)).
	#include<bits/stdc++.h>
	using namespace std;
	#define nx 1001
	int depth[nx];
	int parent[nx];
	int block_sz;
	int jump_parent[nx];
	vector<int> graph[nx];
	void addEdge(int u, int v)
	{
	graph[u].push_back(v);
	graph[v].push_back(u);
	}
	void dfs(int cur, int prev)
	{
	parent[cur] = prev;
	depth[cur] = depth[prev] + 1;
	for(auto x: graph[cur])
	{
	if(x != prev) dfs(x, cur);
	}
	}
	int LCANaive(int u, int v)
	{
	if(u == v) return u;
	if(depth[u] > depth[v]) swap(u,v);
	v = parent[v];
	return LCANaive(u,v);
	}
	void preprocess()
	{
	depth[0] = -1;
	dfs(1,0);
	}
	void dfsSQRT(int cur, int prev)
	{
	depth[cur] = depth[prev] + 1;
	parent[cur] = prev;
	if(depth[cur] % block_sz == 0) jump_parent[cur] = parent[cur];
	else jump_parent[cur] = jump_parent[prev];
	for(auto x: graph[cur])
	{
	if(x != prev) dfs(x, cur);
	}
	}
	int LCASQRT(int u, int v)
	{
	while(jump_parent[u] != jump_parent[v])
	{
	if(depth[u] > depth[v]) swap(u,v);
	v = jump_parent[v];
	}
	/// u and v have same jump_parent
	return LCANaive(u,v);
	}
	int main()
	{
	freopen("in.txt", "r", stdin);a
	int n;
	cin >> n;
	for(int i = 0; i <n; i++)
	{
	int u,v;
	cin >> u >> v;
	//cout << u << " " << v << endl;
	addEdge(u,v);
	}
	preprocess();
	cout << LCANaive(11,8)<<endl;
	cout << LCANaive(3,13)<<endl;
	cout << LCASQRT(11,8)<<endl;
	cout << LCASQRT(3,13)<<endl;
	return 0;
	}
	/*
	12
	1 2
	1 3
	1 4
	2 5
	2 6
	3 7
	4 8
	4 9
	9 10
	9 11
	7 12
	7 13
	*/

view raw lca.cpp hosted with ❤ by GitHub

Share: