Segment tree bug hunt

Questions 1 to 5 of 8

1. 1. A sum tree for six values is allocated like this, and the program fails. build is the recursive sum build from the lesson. ``python a = [4, 1, 7, 2, 9, 3] n = len(a) tree = [0] * (2 * n) build(a, 1, 0, n - 1) ` The error is IndexError: list assignment index out of range`. What is the cause?

   The a list is too short, so a[l] reads past its endEach int takes two list slots, so the tree needs twice as many slotsNode numbers reach 13 for six values, so the 12 slots from 2 * n are too few. Allocate 4 * n insteadThe midpoint (l + r) // 2 goes negative for six values, so a write lands at index 12
2. 2. Predict the output of this program. It builds a max tree over four negative values and asks for three ranges. ``python NONE = 0 def build(a, node, l, r): if l == r: tree[node] = a[l] return mid = (l + r) // 2 build(a, 2 * node, l, mid) build(a, 2 * node + 1, mid + 1, r) tree[node] = max(tree[2 * node], tree[2 * node + 1]) def query(node, l, r, ql, qr): if qr < l or r < ql: return NONE if ql <= l and r <= qr: return tree[node] mid = (l + r) // 2 return max(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr)) a = [-5, -2, -9, -4] tree = [0] * (4 * len(a)) build(a, 1, 0, len(a) - 1) print(f"max of [0,1] = {query(1, 0, 3, 0, 1)}") print(f"max of [1,2] = {query(1, 0, 3, 1, 2)}") print(f"max of [2,3] = {query(1, 0, 3, 2, 3)}") ``

   max of [0,1] = -2 max of [1,2] = 0 max of [2,3] = -9max of [0,1] = 0 max of [1,2] = 0 max of [2,3] = 0max of [0,1] = -2 max of [1,2] = -2 max of [2,3] = -4max of [0,1] = -2 max of [1,2] = 0 max of [2,3] = -4
3. 3. A lazy segment tree gets apply_set of 10 on all four values, then apply_add of 3 on all four. The value at index 0 reads 10 instead of 13. This push function is the cause. ``python def push(node, l, r): mid = (l + r) // 2 left_len = mid - l + 1 right_len = r - mid if add_tag[node] != 0: apply_add(2 * node, left_len, add_tag[node]) apply_add(2 * node + 1, right_len, add_tag[node]) add_tag[node] = 0 if has_set[node]: apply_set(2 * node, left_len, set_val[node]) apply_set(2 * node + 1, right_len, set_val[node]) has_set[node] = False ` apply_set(node, length, v) sets the node's sum to v * length, stores v in set_val, sets has_set to True, and sets add_tag[node] to 0. What is wrong with push`?

   The lengths are swapped, so the left child gets the right child's share of the valuesThe has_set check is placed after mid is computed, so the assign is pushed twiceThe query should never call push on the root, because the root already holds the full sumThe add tag is pushed first, then the assign overwrites the children with 10 and clears their add tags, so the 3 is lost. The assign must go first, then the add
4. 4. In a max or min tree, a query over the whole array returns the root's stored value. Why can a test that only asks for the whole array miss the identity bug and the lazy push order bug?

   A whole-array query returns the root's stored value directly, so it never merges an identity value and never pushes a lazy tag downA whole-array query pushes every tag down to the leaves first, so the children are always correctThe root always stores 0 for the identity, so the whole-array answer is never affectedA whole-array query reads the input list instead of the tree, so it cannot see tree bugs
5. 5. This minimum tree is built for [5, 7, 9, 3, 8]. The query for min of [1,2] returns 0, but 7 is expected. ``python NONE = 0 def query(node, l, r, ql, qr): if qr < l or r < ql: return NONE if ql <= l and r <= qr: return tree[node] mid = (l + r) // 2 return min(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr)) `` Which change fixes the answer?

   Keep NONE at 0 and call query only on ranges that start at index 0Change NONE to float('-inf')Change NONE to float('inf')Change min to max, so the 0 is ignored