Lazy assignments

Questions 1 to 5 of 7

1. 1. Predict the output of this program. It prints one line with four numbers. ``cpp #include <iostream> using ll = long long; struct Node { ll sum; bool has_set; ll set_v; ll add; }; void applySet(Node& n, int len, ll v) { n.sum = v * len; n.has_set = true; n.set_v = v; n.add = 0; } void applyAdd(Node& n, int len, ll d) { n.sum += d * len; n.add += d; } int main() { Node a{6, false, 0, 0}; // holds the values 1, 2, 3 applyAdd(a, 3, 10); applySet(a, 3, 7); std::cout << a.sum << ' ' << a.add << ' '; Node b{6, false, 0, 0}; // holds the values 1, 2, 3 applySet(b, 3, 7); applyAdd(b, 3, 10); std::cout << b.sum << ' ' << b.add << '\n'; } ``

   21 0 51 021 0 51 1021 10 51 051 10 21 0
2. 2. Predict the output of this program. It prints one line with three numbers. ``cpp #include <iostream> using ll = long long; struct Node { ll sum; bool has_set; ll set_v; ll add; }; void applySet(Node& n, int len, ll v) { n.sum = v * len; n.has_set = true; n.set_v = v; n.add = 0; } void applyAdd(Node& n, int len, ll d) { n.sum += d * len; n.add += d; } int main() { Node c{0, false, 0, 0}; // four values, all 0 applySet(c, 4, 5); applyAdd(c, 4, 2); applySet(c, 4, 1); std::cout << c.sum << ' ' << c.set_v << ' ' << c.add << '\n'; } ``

   4 1 028 5 212 1 24 5 2
3. 3. Why does push() give the waiting set to the two children before it gives them the waiting add?

   Pushing the add first would only make the program slowerThe children store only one tag each, so the set must replace the addThe set was applied first, so the add sits on top of it; if the add went down first, the set would overwrite it and the add would be lostThe add tag is always stored in the parent, so it must go down last
4. 4. A node holds a waiting add of 4. Then a set to 1 arrives on that node. What does the node hold afterwards?

   A set to 1 with the add of 4 still on topAn add of 4 only, because the set is ignoredA set to 1 plus the add of 4, pushed to the childrenA set to 1 only, and the add of 4 is dropped
5. 5. Put these steps of an update into the order the recursive code runs them, for a node that is only partly inside the update range.

   Use the arrows to put the steps in order.

   1. 1.If the node's range lies fully inside the update range, apply the change to the node and return↑↓
   2. 2.Recurse into the left child, then into the right child↑↓
   3. 3.Recompute the node's sum from its two children↑↓
   4. 4.Return at once if the node's range does not overlap the update range↑↓
   5. 5.Push the node's waiting tags down to its two children↑↓