Skills101
← All practice quizzes

Quiz: Segment Tree and Fenwick Tree

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Prefix sums answer range-sum questions fast, but break when values change. Segment trees and Fenwick (binary indexed) trees answer range queries and handle updates, both in O(log n).

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    Why are plain prefix sums a poor choice when values change often?

  2. Question 2

    In a segment tree, what does each node store?

  3. Question 3

    During a query, what does a node do if its range is completely inside [L..R]?

  4. Question 4

    What does this print?

    a = [4, 1, 3, 2]
    tree = {}
    def build(lo, hi):
        if lo == hi:
            tree[(lo, hi)] = a[lo]
        else:
            mid = (lo + hi) // 2
            tree[(lo, hi)] = build(lo, mid) + build(mid + 1, hi)
        return tree[(lo, hi)]
    build(0, 3)
    print(tree[(0, 3)], tree[(0, 1)], tree[(2, 3)])
    
  5. Question 5

    In a segment tree for range minimum, what should a completely outside node return?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →