Question presented to candidate: "What is a segment tree? Explain how it answers a range-sum query and a point update, how big the array needs to be, and how you would support adding a value to a whole range. When would you choose it over prefix sums or a Fenwick tree? Show the core in Python."
What a strong answer should cover:
- Each node stores an aggregate of one index range; children split the range in half; about log₂ n levels; any associative merge (sum, min, max, gcd) works.
- Query with the no / total / partial overlap cases and update along one root-to-leaf path, both O(log n); build is O(n).
- The implicit array layout (children 2i and 2i + 1) and why 4n slots are enough.
- Lazy propagation for range updates: tag fully covered nodes and push tags down before visiting children.
- When to use it versus prefix sums (static array), a Fenwick tree (sums with point updates) and a sparse table (static min/max).
- Python details: a list of size
4 * n,hi=Noneinstead of a default that usesself,float('inf')as the min identity, and the recursion depth being only about log₂ n.
Code / implementation expected: Optional — a recursive sum segment tree with update and query in Python; lazy propagation is usually discussed rather than fully coded.