Sparse Table

Note: Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in O(logn), but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compute the answer in O(1) time.

The only drawback of this data structure is, that it can only be used on immutable arrays. This means, that the array cannot be changed between two queries. If any element in the array changes, the complete data structure has to be recomputed.

Rsources:

Tanvir's Blog

E-maxx 

 GeeksForGeeks

HackerEarth 

Tushar Roy Video 

 Topcoder

Codechef

adilet.org_blog_sparse-table 

Implementation: according to (This )  problem 

 

	///https://www.codechef.com/problems/FRMQ
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int a[maxn];
	int sparse[22][maxn];
	int lg[maxn];
	void preprocess(int n)
	{
	for (int i = 0; i < n; i++) sparse[0][i] = i;
	for (int j = 1; (1 << j) <= n; j++) {
	for (int i = 0; i + (1 << j) - 1 < n; i++) {
	int val = (1 << (j - 1));
	if (a[sparse[j - 1][i]] > a[sparse[j - 1][i + val]])
	sparse[j][i] = sparse[j - 1][i];
	else
	sparse[j][i] = sparse[j - 1][i + val];
	}
	}
	return;
	}
	int RMQ(int l, int r)
	{
	int len = r - l + 1;
	int k = lg[len];
	return max(a[sparse[k][l]], a[sparse[k][l + len - (1 << k)]]);
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	//cin >> T;
	T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	lg[1] = 0;
	for (int i = 2; i <= n; i++)
	lg[i] = lg[i >> 1] + 1;
	preprocess(n);
	int m, x, y;
	cin >> m >> x >> y;
	int l = min(x, y);
	int r = max(x, y);
	ll ans = RMQ(l, r);
	for (int i = 1; i < m; i++) {
	x += 7;
	while (x >= (n - 1)) x -= (n - 1);
	y += 11;
	while (y >= n) y -= n;
	l = min(x, y);
	r = max(x, y);
	ans += RMQ(l, r);
	}
	cout << ans << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw sparseTable.cpp hosted with ❤ by GitHub

Share: