Sparse Table क्या है

एक sparse table पहले से तैयार एक cheat sheet जैसा है ताकि आप 'इस range में सबसे छोटा क्या है' जैसे सवालों का तुरंत जवाब दे सकें, जब तक कुछ न बदले।

In this page:

What is Sparse Table
Preprocessing
Range Minimum Query
Limitations
Applications

Syntax

markup

table = [arr[:]]
j = 1
while (1 << j) <= n:
    row = [min(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]) for i in range(n - (1 << j) + 1)]
    table.append(row)
    j += 1

k = (r - l + 1).bit_length() - 1
answer = min(table[k][l], table[k][r - (1 << k) + 1])

What is Sparse Table

एक sparse table एक बार एक fixed, unchanging array को preprocess करता है ताकि बाद की range queries — जैसे 'index 3 और index 9 के बीच minimum value क्या है' — लगभग तुरंत answer हो सकें, कुछ extra memory और एक one-time setup pass की कीमत पर।

उदाहरण: What is Sparse Table

#include <iostream>
using namespace std;
int main() {
	cout << "Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward");
	}
}

print("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward")

#include <stdio.h>
int main() {
	printf("Preprocess a fixed array once, answer range-minimum-style queries almost instantly afterward");
	return 0;
}

Preprocessing

Preprocessing के दौरान, table हर उस range के लिए precomputed answers store करता है जिसकी length दो की power है, single-element ranges से शुरू करके और हर successive level पर range length double करते हुए।

उदाहरण: Preprocessing

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse[3][7];
	for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
	for (int i = 0; i + 1 < 7; i++) sparse[1][i] = min(sparse[0][i], sparse[0][i+1]);
	cout << "Range length 2 starting at 0 (power of two): min = " << sparse[1][0];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,1,7,3,9,8};
		int[][] sparse = new int[3][7];
		for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
		for (int i = 0; i + 1 < 7; i++) sparse[1][i] = Math.min(sparse[0][i], sparse[0][i+1]);
		System.out.println("Range length 2 starting at 0 (power of two): min = " + sparse[1][0]);
	}
}

arr = [2,4,1,7,3,9,8]
sparse = [[0]*7 for _ in range(3)]
sparse[0] = arr[:]
for i in range(6):
    sparse[1][i] = min(sparse[0][i], sparse[0][i+1])
print("Range length 2 starting at 0 (power of two): min =", sparse[1][0])

#include <stdio.h>
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse[3][7];
	for (int i = 0; i < 7; i++) sparse[0][i] = arr[i];
	for (int i = 0; i+1 < 7; i++) sparse[1][i] = sparse[0][i] < sparse[0][i+1] ? sparse[0][i] : sparse[0][i+1];
	printf("Range length 2 starting at 0 (power of two): min = %d", sparse[1][0]);
	return 0;
}

Range Minimum Query

उन operations के लिए जहां दो ranges को दो बार overlap करना answer नहीं बदलता — जैसे minimum, maximum, या GCD — कोई भी arbitrary range table से सिर्फ दो overlapping power-of-two ranges से cover किया जा सकता है, preprocessing के बाद O(1) में answered।

उदाहरण: Range Minimum Query

#include <iostream>
using namespace std;
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int sparse0[7], sparse1[7], sparse2[7];
	for (int i = 0; i < 7; i++) sparse0[i] = arr[i];
	for (int i = 0; i+1 < 7; i++) sparse1[i] = min(sparse0[i], sparse0[i+1]);
	for (int i = 0; i+3 < 7; i++) sparse2[i] = min(sparse1[i], sparse1[i+2]);
	cout << "Range [0,3] covered by two overlapping length-2 ranges, min = " << min(sparse1[0], sparse1[2]);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {2,4,1,7,3,9,8};
		int[] s0 = new int[7], s1 = new int[7];
		for (int i = 0; i < 7; i++) s0[i] = arr[i];
		for (int i = 0; i+1 < 7; i++) s1[i] = Math.min(s0[i], s0[i+1]);
		System.out.println("Range [0,3] covered by two overlapping length-2 ranges, min = " + Math.min(s1[0], s1[2]));
	}
}

arr = [2,4,1,7,3,9,8]
s0 = arr[:]
s1 = [min(s0[i], s0[i+1]) for i in range(6)]
print("Range [0,3] covered by two overlapping length-2 ranges, min =", min(s1[0], s1[2]))

#include <stdio.h>
int main() {
	int arr[] = {2,4,1,7,3,9,8};
	int s0[7], s1[7];
	for (int i = 0; i < 7; i++) s0[i] = arr[i];
	for (int i = 0; i+1 < 7; i++) s1[i] = s0[i] < s0[i+1] ? s0[i] : s0[i+1];
	int result = s1[0] < s1[2] ? s1[0] : s1[2];
	printf("Range [0,3] covered by two overlapping length-2 ranges, min = %d", result);
	return 0;
}

Limitations

चूंकि table original array से एक बार बनाया जाता है और कभी update नहीं होता, sparse tables उन problems के लिए suitable नहीं जहां array values समय के साथ बदलती हैं; जब भी updates चाहिए एक segment tree बेहतर fit है।

उदाहरण: Limitations

#include <iostream>
using namespace std;
int main() {
	cout << "Built once from the original array -- not suitable if array values change; use a segment tree instead";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Built once from the original array -- not suitable if array values change; use a segment tree instead");
	}
}

print("Built once from the original array -- not suitable if array values change; use a segment tree instead")

#include <stdio.h>
int main() {
	printf("Built once from the original array -- not suitable if array values change; use a segment tree instead");
	return 0;
}

Applications

Sparse tables विशेष रूप से तब चमकते हैं जब array fixed हो लेकिन आपको इसके खिलाफ बहुत सारी range queries का जवाब देना हो — one-time preprocessing cost हर range को scratch से scan करने की तुलना में जल्दी अपनी कीमत वसूल करती है।

उदाहरण: Applications

#include <iostream>
using namespace std;
int main() {
	cout << "Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself");
	}
}

print("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself")

#include <stdio.h>
int main() {
	printf("Fixed array, huge number of range queries -- one-time preprocessing quickly pays for itself");
	return 0;
}

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Disjoint Set Union DSU Next Lesson → Monotonic Queue