Add tests for Sparse Table

jakobkogler · jakobkogler · commit dbdb322f7082 · 2018-02-16T23:20:00.000+01:00
diff --git a/src/data_structures/sparse-table.md b/src/data_structures/sparse-table.md
@@ -32,13 +32,13 @@ The size of the 2-dimensional array will be $\text{MAXN} \times (K + 1)$, where
 $\text{K}$ has to satisfy $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor + 1$, because $2^{\lfloor \log_2 \text{MAXN} \rfloor}$ is the biggest power of two range, that we have to support. 
 For arrays with reasonable length ($\le 10^7$ elements), $K = 25$ is a good value. 
 
-```cpp
+```cpp sparsetable_definition
 int st[MAXN][K + 1];
 ```
 
 Because the range $\[i, i + 2^j - 1\]$ of length $2^j$ splits nicely into the ranges $\[i, i + 2^{j - 1} - 1\]$ and $\[i + 2^{j - 1}, i + 2^j - 1\]$, both of length $2^{j - 1}$, we can generate the table efficiently using dynamic programming:
 
-```cpp
+```cpp sparsetable_generation
 for (int i = 0; i < N; i++) 
     st[i][0] = f(array[i]);
 
@@ -58,7 +58,7 @@ For this type of queries, we want to find the sum of all values in a range.
 Therefore the natural definition of the function $f$ is $f(x, y) = x + y$. 
 We can construct the data structure with:
 
-```cpp
+```cpp sparsetable_sum_generation
 long long st[MAXN][K];
 
 for (int i = 0; i < N; i++) 
@@ -72,7 +72,7 @@ for (int j = 1; j <= K; j++)
 To answer the sum query for the range $\[L, R\]$, we iterate over all powers of two, starting from the biggest one.
 As soon as a power of two $2^j$ is smaller or equal to the length of the range ($= R - L + 1$), we process the first the first part of range $\[L, L + 2^j - 1\]$, and continue with the remaining range $\[L + 2^j, R\]$.  
 
-```cpp
+```cpp sparsetable_sum_query
 long long sum = 0;
 for (int j = K; j >= 0; j--) {
     if ((1 << j) <= R - L + 1) {
@@ -98,7 +98,7 @@ $$\min(\text{st}\[L\]\[j\], \text{st}\[R - 2^j + 1][j]) \quad \text{ where } j =
 This requires that we are able to compute $\log_2(R - L + 1)$ fast. 
 You can accomplish that by precomputing all logarithms: 
 
-```cpp
+```cpp sparse_table_log_table
 int log[MAXN+1];
 log[1] = 0;
 for (int i = 2; i <= MAXN; i++) 
@@ -107,7 +107,7 @@ for (int i = 2; i <= MAXN; i++)
 
 Afterwards we need to precompute the Sparse Table structure. This time we define $f$ with $f(x, y) = \min(x, y)$. 
 
-```cpp
+```cpp sparse_table_minimum_generation
 int st[MAXN][K];
 
 for (int i = 0; i < N; i++) 
@@ -120,7 +120,7 @@ for (int j = 1; j <= K; j++)
 
 And the minimum of a range $\[L, R\]$ can be computed with:
 
-```cpp
+```cpp sparse_table_minimum_query
 int j = log[R - L + 1];
 int minimum = min(st[L][j], st[R - (1 << j) + 1][j]);
 ```
diff --git a/test/test_sparsetable.cpp b/test/test_sparsetable.cpp
@@ -0,0 +1,71 @@
+#include <vector>
+#include <numeric>
+#include <cassert>
+
+const int MAXN = 15;
+const int K = 5;
+
+const int N = MAXN;
+const std::vector<int> array = {19, 16, 2, 15, 2, 12, 13, 13, 18, 14, 0, 4, 17, 17, 4};
+
+void test_generic_sparsetable() {
+    auto f = [&](int x, int y=0) { return x + y; };
+
+    #include "sparsetable_definition.h"
+    #include "sparsetable_generation.h"
+
+    auto sum_query = [&](int L, int R) {
+        #include "sparsetable_sum_query.h"
+        return sum;
+    };
+
+    for (int L = 0; L < N; L++) {
+        for (int R = L; R < N; R++) {
+            int sum = std::accumulate(array.begin() + L, array.begin() + R + 1, 0);
+            assert(sum == sum_query(L, R));
+        }
+    }
+}
+
+void test_range_sum_sparsetable() {
+    #include "sparsetable_sum_generation.h"
+
+    auto sum_query = [&](int L, int R) {
+        #include "sparsetable_sum_query.h"
+        return sum;
+    };
+
+    for (int L = 0; L < N; L++) {
+        int sum = 0;
+        for (int R = L; R < N; R++) {
+            sum += array[R];
+            assert(sum == sum_query(L, R));
+        }
+    }
+}
+
+void test_range_minimum_sparsetable() {
+    using std::min;
+
+    #include "sparse_table_log_table.h"
+    #include "sparse_table_minimum_generation.h"
+
+    auto minimum_query = [&](int L, int R) {
+        #include "sparse_table_minimum_query.h"
+        return minimum;
+    };
+
+    for (int L = 0; L < N; L++) {
+        int minimum = array[L];
+        for (int R = L; R < N; R++) {
+            minimum = min(minimum, array[R]);
+            assert(minimum == minimum_query(L, R));
+        }
+    }
+}
+
+int main() {
+    test_generic_sparsetable();
+    test_range_sum_sparsetable();
+    test_range_minimum_sparsetable();
+}
