Segment trees and offline sweeps

Questions 1 to 5 of 7

1. 1. An AI wrote a max-subarray segment tree with the identity {sum 0, best prefix 0, best suffix 0, best 0}. A query on the range [-3, -1, -2] returns 0. What is wrong?

   Nothing. An empty segment has sum 0, so 0 is always a valid answer for a subarray query.The merge overflows on negative values, because the identity should be the largest 32-bit integer.The identity adds an empty segment as a candidate with best value 0. A non-empty subarray must be chosen, so the right answer is -1, the largest single element.The tree returns the leftmost value instead of the best one, so the answer should be -3.
2. 2. Which properties does a segment tree need from its merge operation, to answer range queries with a bottom-up or recursive layout?

   Pick every answer that is true.

   The merge is associative, so the tree can split a range into pieces and merge them in any grouping.There is an identity element, which is the answer for an empty range.The merge is commutative, so the two children can be swapped without changing the answer.The operands stay in array order, left before right, when two parts are merged.
3. 3. A node has a pending tag "add 10", written as the map f = (1, 10), meaning x -> 1 * x + 10. Then a new tag "assign 7" arrives, written as g = (0, 7). The rule for composing is: the old tag goes first, so the combined map is (g.a * f.a, g.a * f.b + g.b). Apply the combined tag to a child value of 1. What is the result?

   Type a number.

4. 4. An AI wrote a lazy segment tree update. When a node only partly overlaps the update range, its code calls the two children first, then pushes the node's pending tag to them. What goes wrong?

   Nothing, because a sum does not depend on the order of updates.The tree uses twice as much memory, because each child stores its own copy of the tag.The update is applied to a child before its old tag, so the old tag reaches the child after the new change. The two changes are applied in the wrong order and the sums are wrong.The code is slower, but the sums are right, because the push only costs an extra O(log n) work.
5. 5. Match each part of the offline distinct-count sweep with what it does.

   Choose the matching item for each row.

   Last-occurrence flagChoose…Subtract 1 at the old position before adding 1 at the new position, so the value is not counted twiceThe number of flags inside the range [l, r)The sweep only moves forward, so each position is added to the tree onceA 1 at a position that is the last index of its value among the positions the sweep has passedMoving a flagChoose…Subtract 1 at the old position before adding 1 at the new position, so the value is not counted twiceThe number of flags inside the range [l, r)The sweep only moves forward, so each position is added to the tree onceA 1 at a position that is the last index of its value among the positions the sweep has passedSorting queries by rChoose…Subtract 1 at the old position before adding 1 at the new position, so the value is not counted twiceThe number of flags inside the range [l, r)The sweep only moves forward, so each position is added to the tree onceA 1 at a position that is the last index of its value among the positions the sweep has passedAnswer prefix(r - 1) - prefix(l - 1)Choose…Subtract 1 at the old position before adding 1 at the new position, so the value is not counted twiceThe number of flags inside the range [l, r)The sweep only moves forward, so each position is added to the tree onceA 1 at a position that is the last index of its value among the positions the sweep has passed