Sparse table and GCD

Questions 1 to 5 of 8

1. 1. Predict the output of this program. It prints one line with four numbers. ``cpp #include <algorithm> #include <bit> #include <cstddef> #include <iostream> #include <vector> class SparseMin { public: explicit SparseMin(const std::vector<int>& values) { const std::size_t n = values.size(); table_.push_back(values); for (std::size_t len = 2; len <= n; len *= 2) { const std::vector<int>& prev = table_.back(); const std::size_t half = len / 2; std::vector<int> level(n - len + 1); for (std::size_t i = 0; i + len <= n; ++i) { level[i] = std::min(prev[i], prev[i + half]); } table_.push_back(std::move(level)); } } int query(std::size_t l, std::size_t r) const { const std::size_t len = r - l + 1; const std::size_t k = std::bit_width(len) - 1; return std::min(table_[k][l], table_[k][r + 1 - (std::size_t{1} << k)]); } private: std::vector<std::vector<int>> table_; }; int main() { const SparseMin sp({9, 4, 7, 2, 8, 6}); std::cout << sp.query(0, 5) << ' ' << sp.query(1, 2) << ' ' << sp.query(1, 4) << ' ' << sp.query(4, 5) << '\n'; } ``

   2 4 7 69 4 2 62 4 2 82 4 2 6
2. 2. Predict the output of this program. It prints one line with two numbers. ``cpp #include <iostream> #include <numeric> #include <vector> int main() { const std::vector<int> a = {12, 18, 8}; int with_zero = 0; // identity for gcd int with_one = 1; // wrong start value for (int x : a) { with_zero = std::gcd(with_zero, x); with_one = std::gcd(with_one, x); } std::cout << with_zero << ' ' << with_one << '\n'; } ``

   2 21 12 10 0
3. 3. Why can a sparse table answer a range-minimum query with two overlapping blocks, while the same trick gives a wrong answer for a range sum?

   A minimum is faster to compute than a sum, so the table only stores minimumsRepeating a value does not change a minimum, but counting a value twice adds it twice to a sumSums cannot be stored in a table with levels, because the levels hold only whole numbersMinimums can be negative and sums cannot, so the blocks never overlap for sums
4. 4. A sparse table is built for an array of 8 values. Then one value in the array is changed, and no rebuild happens. What do later queries do?

   They sum the old and new values before taking the minimumThey update only the affected levels in O(log n) time, so the answers stay correctThey drop the changed position and answer with the rest of the rangeThey keep the old stored minimums, so answers can be wrong until the table is rebuilt
5. 5. How many levels does a sparse table have for an array of length 16?

   Type a number.