Segment tree bug hunt

Questions 1 to 5 of 8

1. 1. The minimum tree's query below returns 0 for any node that lies outside the requested range. Which change makes query(2, 3) on 5, 3, 8, 6 return 6? ``cpp long long query(int node, int lo, int hi, int l, int r) const { if (r < lo || hi < l) return 0; if (l <= lo && hi <= r) return t_[node]; int mid = lo + (hi - lo) / 2; return std::min(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r)); } ``

   Return 1 instead of 0, because 1 is the neutral value for every operationReturn std::numeric_limits<long long>::max() instead of 0, because the largest possible number never changes a std::min resultKeep 0 and skip the outside child when l is 0Return t_[node] instead of 0, because the stored minimum is always the right answer
2. 2. The assign function below is the lazy range-assign from the lab. After assign(0, 3, 5) and then assign(0, 1, 1), sum(0, 3) prints 20 instead of 12. Which change fixes it? ``cpp void assign(int node, int lo, int hi, int l, int r, long long v) { if (r < lo || hi < l) return; if (l <= lo && hi <= r) { apply(node, lo, hi, v); return; } int mid = lo + (hi - lo) / 2; assign(2 * node, lo, mid, l, r, v); assign(2 * node + 1, mid + 1, hi, l, r, v); push(node, lo, hi); t_[node].total = t_[2 * node].total + t_[2 * node + 1].total; } ``

   Delete the push call, because the children already hold the right valuesCall t_[node].tag.reset() before the recursive calls, so the tag is not pushed twiceMove push(node, lo, hi) above the two recursive calls, so the children get the old tag before they changeCall push only when the node is fully inside the request, because partial nodes need no tag
3. 3. A sum segment tree stores its nodes in a vector sized 2 * a.size(), and its build uses t_.at(node), with the root at node 1. For which input does the constructor throw std::out_of_range? ``cpp class SumTree { public: explicit SumTree(const std::vector<long long>& a) : n_(static_cast<int>(a.size())), t_(2 * a.size()) { build(1, 0, n_ - 1, a); } private: void build(int node, int lo, int hi, const std::vector<long long>& a) { if (lo == hi) { t_.at(node) = a[lo]; return; } int mid = lo + (hi - lo) / 2; build(2 * node, lo, mid, a); build(2 * node + 1, mid + 1, hi, a); t_.at(node) = t_.at(2 * node) + t_.at(2 * node + 1); } int n_; std::vector<long long> t_; }; ``

   {7, 8, 9}{1, 2, 3, 4}{1, 2, 3, 4, 5}{1, 2, 3, 4, 5, 6}
4. 4. A max tree is built over the values -5, -3, and its query is below. query(0, 0) returns 0 instead of -5. What is the cause? ``cpp long long query(int node, int lo, int hi, int l, int r) const { if (r < lo || hi < l) return 0; if (l <= lo && hi <= r) return t_[node]; int mid = lo + (hi - lo) / 2; return std::max(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r)); } ``

   0 is used as the answer for an outside node, and 0 is larger than -5, so std::max keeps it. The neutral value for max is the smallest possible number.The lazy tag was pushed after the children changed, so the leaf for position 0 lost its valueThe vector is too small, so the build reads past the end and returns 0The leaf for position 0 was never built, so it holds the default value 0
5. 5. The program below prints two lines. What does it print? ``cpp #include <algorithm> #include <iostream> #include <vector> class MinTree { public: explicit MinTree(const std::vector<long long>& a) : n_(static_cast<int>(a.size())), t_(4 * a.size()) { build(1, 0, n_ - 1, a); } long long query(int l, int r) const { return query(1, 0, n_ - 1, l, r); } private: void build(int node, int lo, int hi, const std::vector<long long>& a) { if (lo == hi) { t_[node] = a[lo]; return; } int mid = lo + (hi - lo) / 2; build(2 * node, lo, mid, a); build(2 * node + 1, mid + 1, hi, a); t_[node] = std::min(t_[2 * node], t_[2 * node + 1]); } long long query(int node, int lo, int hi, int l, int r) const { if (r < lo || hi < l) return 0; if (l <= lo && hi <= r) return t_[node]; int mid = lo + (hi - lo) / 2; return std::min(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r)); } int n_; std::vector<long long> t_; }; int main() { MinTree mt({5, 3}); std::cout << mt.query(0, 0) << '\n'; std::cout << mt.query(1, 1) << '\n'; } ``

   5, then 30, then 00, then 33, then 0