Dynamic trees and 2D sums

Questions 1 to 5 of 7

1. 1. Predict the output of this program. ``python LO = 1 HI = 1_000_000_000 class DynamicSegmentTree: def __init__(self): self.left = [0] # index 0 means no node self.right = [0] self.sum = [0] self.root = 0 def nodes_used(self): return len(self.sum) - 1 def _new_node(self): self.left.append(0) self.right.append(0) self.sum.append(0) return len(self.sum) - 1 def add(self, pos, delta): self.root = self._add_at(self.root, LO, HI, pos, delta) def _add_at(self, node, lo, hi, pos, delta): if node == 0: node = self._new_node() self.sum[node] += delta if lo == hi: return node mid = lo + (hi - lo) // 2 if pos <= mid: self.left[node] = self._add_at(self.left[node], lo, mid, pos, delta) else: self.right[node] = self._add_at(self.right[node], mid + 1, hi, pos, delta) return node def query(self, l, r): return self._query_at(self.root, LO, HI, l, r) def _query_at(self, node, lo, hi, l, r): if node == 0 or r < lo or hi < l: return 0 if l <= lo and hi <= r: return self.sum[node] mid = lo + (hi - lo) // 2 return (self._query_at(self.left[node], lo, mid, l, r) + self._query_at(self.right[node], mid + 1, hi, l, r)) tree = DynamicSegmentTree() tree.add(5, 1) print("after one insert:", tree.nodes_used()) tree.add(999_999_999, 1) tree.add(6, 2) print("nodes used:", tree.nodes_used()) print("query(1, 100):", tree.query(1, 100)) print("query(6, 1000000000):", tree.query(6, 1_000_000_000)) print("query(7, 999999998):", tree.query(7, 999_999_998)) ``

   after one insert: 31 nodes used: 62 query(1, 100): 3 query(6, 1000000000): 3 query(7, 999999998): 0after one insert: 30 nodes used: 62 query(1, 100): 3 query(6, 1000000000): 3 query(7, 999999998): 0after one insert: 31 nodes used: 61 query(1, 100): 3 query(6, 1000000000): 3 query(7, 999999998): 0after one insert: 31 nodes used: 62 query(1, 100): 2 query(6, 1000000000): 3 query(7, 999999998): 0
2. 2. Predict the output of this program. ``python def build_prefix(g, n, m): p = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): p[i][j] = g[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] return p def rect_from_prefix(p, r1, c1, r2, c2): return p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1] grid = [ [0, 0, 0, 0], [0, 4, 1, 3], [0, 2, 5, 6], ] p = build_prefix(grid, 2, 3) print(p[2][3]) print(p[1][2]) print(rect_from_prefix(p, 2, 2, 2, 3)) print(rect_from_prefix(p, 1, 2, 2, 2)) ``

   21 5 11 521 4 11 621 5 12 621 5 11 6
3. 3. A dynamic segment tree over the range 1 to 1000000000 creates at most how many nodes for one insert?

   130311000000000
4. 4. Why does query return 0 when it reaches a child whose index is 0?

   Node 0 stores a sum of -1, which marks that the part is emptyNo node was ever created for that part, so every position there holds 0, and creating one would waste memoryThe query creates the missing child first, and then reads its sum of 0Index 0 is the left child, so the query skips it and reads only the right child
5. 5. Which statements about the 2D prefix table and the 2D Fenwick tree are true? Pick all that apply.

   Pick every answer that is true.

   An update in the 2D Fenwick tree walks through about 10 slots per dimension for a grid of 1000 by 1000 cellsIndex 0 is a valid starting position for the Fenwick loops, because i & -i is 1 when i is 0A rectangle question on the 2D Fenwick tree uses four prefix queriesAfter one cell changes, the prefix table must be rebuilt, but the Fenwick tree does not need a rebuild