Última atividade 5 days ago

Interview prep notes

segtree.md Bruto

Segment Trees for Interviews: Range Queries with Updates

Prefix sums answer range-sum queries in O(1), but a single update costs O(n). When a problem mixes point updates and range queries (LeetCode 307, Range Sum Query - Mutable), a segment tree gives O(log n) for both.

Iterative segment tree (compact version)

class SegTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = nums
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, i, val):
        i += self.n
        self.t[i] = val
        while i > 1:
            i //= 2
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def query(self, l, r):            # inclusive l..r
        res, l, r = 0, l + self.n, r + self.n + 1
        while l < r:
            if l & 1: res += self.t[l]; l += 1
            if r & 1: r -= 1; res += self.t[r]
            l //= 2; r //= 2
        return res

Swap + for min, max or gcd to support other associative operations.

When an interviewer expects it

  • Range updates and range queries: mention lazy propagation.
  • Counting inversions or "count of smaller numbers after self" (315): a segment tree or Fenwick tree over value ranks.

Fenwick tree comparison

A Fenwick (binary indexed) tree is shorter to write and enough for prefix sums, but a segment tree handles min/max and lazy range updates more naturally. Saying which you'd pick and why is often worth more than the code.


Disclosure: I work on Linkjob.ai, which offers real-time interview help.