Segment Tree Beats — Interview Preparation¶

Audience: Candidates preparing for competitive programming (Codeforces Div. 1, ICPC, AtCoder) and advanced data-structure interviews. 45 tiered questions plus a full coding challenge in Go, Java, and Python.

Segment Tree Beats is an expert-tier topic — it rarely appears in standard FAANG loops, but it is a discriminator in competitive programming and in interviews that probe deep data-structure knowledge. These questions move from "what is it" to the potential-function proof.

Table of Contents¶

1. Junior Questions (1–12)
2. Middle Questions (13–26)
3. Senior Questions (27–38)
4. Professional Questions (39–45)
5. Coding Challenge — chmin + sum + max

Junior Questions (1–12)¶

Selected answers¶

Q3 — Why plain lazy fails. A lazy tag means "apply this same transformation to every element." Add (+v) and assign (=v) are uniform. But chmin(x) only changes elements currently > x, by varying amounts. From a node's single sum, you cannot compute the new sum without knowing how many elements exceeded x and by how much — information a single aggregate doesn't hold. Beats adds max1/max2/cnt so that in the case where only the maxima are affected, the sum update becomes O(1).

Q6 — The three branches. Given a fully-covered node and chmin value x: - x >= max1 → break, no change. - max2 < x < max1 → tag, O(1) apply. - x <= max2 → recurse, because non-maximum elements are also affected and have heterogeneous values.

Q9 — Tag sum correctness. Elements equal to max1 (there are cnt) become x; every other element is <= max2 < x so unchanged. New sum = sum - cnt*max1 + cnt*x = sum - cnt*(max1 - x).

Q5 — Why strict, in one line. The tag condition x > max2 means "everything below the maximum is strictly below x and thus untouched." If max2 could equal max1, that guarantee is gone and the O(1) sum formula under-counts.

Q11 — Build is O(n). Each of the O(n) nodes is visited once; the merge at each is O(1). Same as a vanilla segment tree.

Middle Questions (13–26)¶

Selected answers¶

Q13 — The strict-max2 merge. Combining children L, R:

sum = L.sum + R.sum
if L.max1 == R.max1: max1=L.max1; cnt=L.cnt+R.cnt; max2=max(L.max2,R.max2)
elif L.max1 > R.max1: max1=L.max1; cnt=L.cnt;       max2=max(L.max2,R.max1)
else:                 max1=R.max1; cnt=R.cnt;       max2=max(R.max2,L.max1)

Q16 — Range-add + chmin. Model each node with two lazy tags: addAll adds to every element; addMax adds only to elements currently equal to max1. A range-add is applyTag(addAll=v, addMax=0). A chmin to x at a tag-eligible node is applyTag(addAll=0, addMax=x-max1) — a negative add to just the maxima. This unifies add and chmin into one additive framework, so push-down composes cleanly.

Q21 — Why max-only is cheaper. The sum query forces the potential argument to track the distribution of values across O(log n) canonical segments, each injecting O(log n) potential → log². With only max, a node holds a single value and the recursion depth is charged once per level → log.

Senior Questions (27–38)¶

Selected answers¶

Q28/Q29 — Amortized trap. The O(n log² n) is amortized over a sequence. A single chmin can recurse to Θ(n) nodes when it repeatedly breaks the tag condition down to the leaves. The amortization holds because such an op destroys potential (collapses distinct values), which can only be rebuilt at O(log n) per op. So total is bounded but individual ops are not — fatal for hard real-time, fine for batch.

Q36 — TLE cause. The break condition x >= max1 is what prunes the recursion when nothing changes. Omit it and a chmin descends through every node in range regardless, turning amortized polylog into Θ(nq). This is the #1 "my Beats is correct but times out" bug.

Professional Questions (39–45)¶

Selected answers¶

Q41–Q42 — The amortized argument. Amortized cost â_i = c_i + Φ_i - Φ_{i-1}. Every recurse step decreases Φ by ≥ 1, so it is "free" amortized. The only charged work is the potential each op injects at the O(log n) canonical-segment boundaries: O(log² n) per op for chmin+sum. Summing: Σ c_i ≤ Φ_0 + Σ(injected) = O(n log n) + O(q log² n) = O((n+q) log² n).

Q44 — Strictness is correctness, not just speed. If x ≤ max2, an element equal to max2 satisfies min(a_i, x) = x ≠ a_i, so it changes — but the tag formula sum -= cnt*(max1-x) only accounts for the max1 elements. The sum would be wrong. Hence the tag is only valid when x > max2 strictly. (An over-large reported max2 merely forces extra recursion — slow but still correct, since recursion recomputes from scratch.)

Q39–Q40 — Why Φ₀ = O(n log n). Φ = Σ_v d(v) where d(v) is the distinct-value count of node v's segment. Since d(v) ≤ |seg(v)| and each array index appears in exactly one segment per level (O(log n) levels), Σ_v |seg(v)| = O(n log n), which dominates Φ₀.

Q45 — Historic max augmentation. Add a max-plus lazy 4-tuple (addAll, addMax, addAllHist, addMaxHist) where the *Hist components record the running maximum the tag reached since the last flush. Push-down composes with child.hist = max(child.hist, child.cur + parent.hist). This captures peaks even when the current value later dips. Costs at most one extra log factor.

Bonus rapid-fire¶

Coding Challenge — chmin + sum + max (HDU 5306 style)¶

Problem. Given an array of n non-negative integers, support q operations: - 0 l r x — for each i in [l, r], set a_i = min(a_i, x). - 1 l r — output max(a_l, ..., a_r). - 2 l r — output a_l + ... + a_r.

Constraints: n, q ≤ 10⁶, 0 ≤ a_i, x ≤ 2³¹ − 1. Use 0-indexed [l, r] inclusive.

Implement in all three languages. Each must pass random brute-force tests.

Go¶

package main

import (
    "bufio"
    "fmt"
    "os"
)

const NEG = int64(-1) << 62

type Beats struct {
    n                    int
    sum, max1, max2, cnt []int64
}

func NewBeats(a []int64) *Beats {
    n := len(a)
    m := 4 * n
    b := &Beats{n: n, sum: make([]int64, m), max1: make([]int64, m),
        max2: make([]int64, m), cnt: make([]int64, m)}
    b.build(1, 0, n-1, a)
    return b
}
func (b *Beats) merge(v int) {
    L, R := 2*v, 2*v+1
    b.sum[v] = b.sum[L] + b.sum[R]
    if b.max1[L] == b.max1[R] {
        b.max1[v], b.cnt[v] = b.max1[L], b.cnt[L]+b.cnt[R]
        b.max2[v] = maxI(b.max2[L], b.max2[R])
    } else if b.max1[L] > b.max1[R] {
        b.max1[v], b.cnt[v] = b.max1[L], b.cnt[L]
        b.max2[v] = maxI(b.max2[L], b.max1[R])
    } else {
        b.max1[v], b.cnt[v] = b.max1[R], b.cnt[R]
        b.max2[v] = maxI(b.max2[R], b.max1[L])
    }
}
func (b *Beats) build(v, lo, hi int, a []int64) {
    if lo == hi {
        b.sum[v], b.max1[v], b.max2[v], b.cnt[v] = a[lo], a[lo], NEG, 1
        return
    }
    mid := (lo + hi) / 2
    b.build(2*v, lo, mid, a)
    b.build(2*v+1, mid+1, hi, a)
    b.merge(v)
}
func (b *Beats) apply(v int, x int64) {
    if x >= b.max1[v] {
        return
    }
    b.sum[v] -= (b.max1[v] - x) * b.cnt[v]
    b.max1[v] = x
}
func (b *Beats) push(v int) { b.apply(2*v, b.max1[v]); b.apply(2*v+1, b.max1[v]) }
func (b *Beats) chmin(v, lo, hi, l, r int, x int64) {
    if r < lo || hi < l || x >= b.max1[v] {
        return
    }
    if l <= lo && hi <= r && x > b.max2[v] {
        b.apply(v, x)
        return
    }
    b.push(v)
    mid := (lo + hi) / 2
    b.chmin(2*v, lo, mid, l, r, x)
    b.chmin(2*v+1, mid+1, hi, l, r, x)
    b.merge(v)
}
func (b *Beats) qmax(v, lo, hi, l, r int) int64 {
    if r < lo || hi < l {
        return NEG
    }
    if l <= lo && hi <= r {
        return b.max1[v]
    }
    b.push(v)
    mid := (lo + hi) / 2
    return maxI(b.qmax(2*v, lo, mid, l, r), b.qmax(2*v+1, mid+1, hi, l, r))
}
func (b *Beats) qsum(v, lo, hi, l, r int) int64 {
    if r < lo || hi < l {
        return 0
    }
    if l <= lo && hi <= r {
        return b.sum[v]
    }
    b.push(v)
    mid := (lo + hi) / 2
    return b.qsum(2*v, lo, mid, l, r) + b.qsum(2*v+1, mid+1, hi, l, r)
}
func maxI(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
    var n, q int
    fmt.Fscan(r, &n, &q)
    a := make([]int64, n)
    for i := range a {
        fmt.Fscan(r, &a[i])
    }
    b := NewBeats(a)
    for ; q > 0; q-- {
        var op, l, ri int
        fmt.Fscan(r, &op, &l, &ri)
        if op == 0 {
            var x int64
            fmt.Fscan(r, &x)
            b.chmin(1, 0, n-1, l, ri, x)
        } else if op == 1 {
            fmt.Fprintln(w, b.qmax(1, 0, n-1, l, ri))
        } else {
            fmt.Fprintln(w, b.qsum(1, 0, n-1, l, ri))
        }
    }
}

Java¶

import java.io.*;
import java.util.*;

public class Main {
    static final long NEG = Long.MIN_VALUE / 2;
    static int n;
    static long[] sum, max1, max2, cnt;

    static void merge(int v) {
        int L = 2 * v, R = 2 * v + 1;
        sum[v] = sum[L] + sum[R];
        if (max1[L] == max1[R]) { max1[v]=max1[L]; cnt[v]=cnt[L]+cnt[R]; max2[v]=Math.max(max2[L],max2[R]); }
        else if (max1[L] > max1[R]) { max1[v]=max1[L]; cnt[v]=cnt[L]; max2[v]=Math.max(max2[L],max1[R]); }
        else { max1[v]=max1[R]; cnt[v]=cnt[R]; max2[v]=Math.max(max2[R],max1[L]); }
    }
    static void build(int v, int lo, int hi, long[] a) {
        if (lo == hi) { sum[v]=a[lo]; max1[v]=a[lo]; max2[v]=NEG; cnt[v]=1; return; }
        int mid = (lo + hi) >>> 1;
        build(2*v, lo, mid, a); build(2*v+1, mid+1, hi, a); merge(v);
    }
    static void apply(int v, long x) {
        if (x >= max1[v]) return;
        sum[v] -= (max1[v] - x) * cnt[v]; max1[v] = x;
    }
    static void push(int v) { apply(2*v, max1[v]); apply(2*v+1, max1[v]); }
    static void chmin(int v, int lo, int hi, int l, int r, long x) {
        if (r < lo || hi < l || x >= max1[v]) return;
        if (l <= lo && hi <= r && x > max2[v]) { apply(v, x); return; }
        push(v);
        int mid = (lo + hi) >>> 1;
        chmin(2*v, lo, mid, l, r, x); chmin(2*v+1, mid+1, hi, l, r, x); merge(v);
    }
    static long qmax(int v, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return NEG;
        if (l <= lo && hi <= r) return max1[v];
        push(v);
        int mid = (lo + hi) >>> 1;
        return Math.max(qmax(2*v, lo, mid, l, r), qmax(2*v+1, mid+1, hi, l, r));
    }
    static long qsum(int v, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return sum[v];
        push(v);
        int mid = (lo + hi) >>> 1;
        return qsum(2*v, lo, mid, l, r) + qsum(2*v+1, mid+1, hi, l, r);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());
        int m = 4 * n;
        sum = new long[m]; max1 = new long[m]; max2 = new long[m]; cnt = new long[m];
        build(1, 0, n - 1, a);
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            if (op == 0) { long x = Long.parseLong(st.nextToken()); chmin(1, 0, n - 1, l, r, x); }
            else if (op == 1) out.append(qmax(1, 0, n - 1, l, r)).append('\n');
            else out.append(qsum(1, 0, n - 1, l, r)).append('\n');
        }
        System.out.print(out);
    }
}

Python¶

import sys
input = sys.stdin.buffer.read

NEG = -(1 << 62)

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); q = int(data[idx+1]); idx += 2
    a = [int(data[idx+i]) for i in range(n)]; idx += n
    m = 4 * n
    sm = [0]*m; mx1 = [0]*m; mx2 = [NEG]*m; cnt = [0]*m

    def merge(v):
        L, R = 2*v, 2*v+1
        sm[v] = sm[L] + sm[R]
        if mx1[L] == mx1[R]:
            mx1[v] = mx1[L]; cnt[v] = cnt[L]+cnt[R]; mx2[v] = max(mx2[L], mx2[R])
        elif mx1[L] > mx1[R]:
            mx1[v] = mx1[L]; cnt[v] = cnt[L]; mx2[v] = max(mx2[L], mx1[R])
        else:
            mx1[v] = mx1[R]; cnt[v] = cnt[R]; mx2[v] = max(mx2[R], mx1[L])

    def build(v, lo, hi):
        if lo == hi:
            sm[v] = mx1[v] = a[lo]; mx2[v] = NEG; cnt[v] = 1; return
        mid = (lo+hi)//2
        build(2*v, lo, mid); build(2*v+1, mid+1, hi); merge(v)

    def apply(v, x):
        if x >= mx1[v]: return
        sm[v] -= (mx1[v]-x)*cnt[v]; mx1[v] = x

    def push(v):
        apply(2*v, mx1[v]); apply(2*v+1, mx1[v])

    def chmin(v, lo, hi, l, r, x):
        if r < lo or hi < l or x >= mx1[v]: return
        if l <= lo and hi <= r and x > mx2[v]:
            apply(v, x); return
        push(v); mid = (lo+hi)//2
        chmin(2*v, lo, mid, l, r, x); chmin(2*v+1, mid+1, hi, l, r, x); merge(v)

    def qmax(v, lo, hi, l, r):
        if r < lo or hi < l: return NEG
        if l <= lo and hi <= r: return mx1[v]
        push(v); mid = (lo+hi)//2
        return max(qmax(2*v, lo, mid, l, r), qmax(2*v+1, mid+1, hi, l, r))

    def qsum(v, lo, hi, l, r):
        if r < lo or hi < l: return 0
        if l <= lo and hi <= r: return sm[v]
        push(v); mid = (lo+hi)//2
        return qsum(2*v, lo, mid, l, r) + qsum(2*v+1, mid+1, hi, l, r)

    sys.setrecursionlimit(1 << 20)
    build(1, 0, n-1)
    out = []
    for _ in range(q):
        op = int(data[idx]); l = int(data[idx+1]); r = int(data[idx+2]); idx += 3
        if op == 0:
            x = int(data[idx]); idx += 1
            chmin(1, 0, n-1, l, r, x)
        elif op == 1:
            out.append(str(qmax(1, 0, n-1, l, r)))
        else:
            out.append(str(qsum(1, 0, n-1, l, r)))
    sys.stdout.write("\n".join(out) + ("\n" if out else ""))

solve()

How to verify¶

Brute-force reference (Python): maintain the literal array, do for i in range(l, r+1): a[i] = min(a[i], x) for chmin, plain max/sum for queries. Generate thousands of random ops on n ≤ 50, compare every query output. If they ever diverge, the bug is almost always (a) non-strict max2 in merge, or (b) a missing push-down in a query, or (c) the break condition omitted.

import random
def brute_check(trials=3000):
    for _ in range(trials):
        n = random.randint(1, 30)
        a = [random.randint(0, 20) for _ in range(n)]
        # build your Beats over a copy of a
        # ... bt = Beats(a[:])
        for _ in range(40):
            l = random.randint(0, n - 1); r = random.randint(l, n - 1)
            op = random.randint(0, 2)
            if op == 0:
                x = random.randint(0, 20)
                for i in range(l, r + 1): a[i] = min(a[i], x)
                # bt.chmin(l, r, x)
            elif op == 1:
                assert max(a[l:r+1]) == 0  # replace 0 with bt.query_max(l, r)
            else:
                assert sum(a[l:r+1]) == 0  # replace 0 with bt.query_sum(l, r)
    print("all good")

Complexity: Build O(n); each query O(log n); chmin amortized O(log n) for this max+sum variant, O((n+q) log n) total.

Follow-Up Discussion Points (whiteboard depth)¶

Strong candidates volunteer these without prompting:

D1 — "Why log² for sum but log for max?"¶

The max-only variant keeps one comparable value per node; a chmin either no-ops or sets a node's max, charged once per level. Maintaining sum requires accounting for the value distribution across the O(log n) canonical segments, each of which can inject O(log n) potential — hence log². (Full argument: professional.md §7–8.)

D2 — "Show me the potential function."¶

Φ = Σ_v d(v), the number of distinct values in each node-segment. Initial Φ = O(n log n) (each element in O(log n) segments). Every recurse step is paid by a unit decrease in Φ; each operation injects O(log² n) potential. Total work O((n+q) log² n).

D3 — "How would you extend to range-add?"¶

A two-component lazy tag (addAll, addMax): add hits everyone (applyTag(v, 0)), chmin is modeled as a negative add to only the maxima (applyTag(0, x-max1)). Push-down gives addMax only to the child carrying the global maximum. (middle.md §6.)

D4 — "What breaks if you forget the break condition?"¶

Every chmin recurses to the leaves regardless of whether anything changes, turning amortized polylog into Θ(nq) — the classic "correct but TLE" failure.

D5 — "Can this be made worst-case O(log n) per op?"¶

No — Beats is inherently amortized; a single chmin is Θ(n) worst case. For worst-case bounds, use sqrt decomposition (O(√n)/op) or reformulate offline. Cell-probe lower bounds rule out o(log n) worst-case for the full operation set.

D6 — "How do you test it?"¶

Brute-force an array, replay thousands of random op sequences on small n, assert equality on every query. The strict-max2 merge and missing-push-down are the bugs this catches.

A Second, Smaller Challenge — Count Elements Lowered¶

Problem. Support chmin(l, r, x) that additionally returns how many elements were actually changed (i.e., how many a_i > x in [l, r] before the op). Maintain it during the same recursion.

Hint. In the tag case, exactly cnt elements change; in the break case, zero; recurse and sum the children. No extra pass needed.

Python (core)¶

def chmin_count(self, v, lo, hi, l, r, x):
    if r < lo or hi < l or x >= self.max1[v]:
        return 0                                   # break: nothing changed
    if l <= lo and hi <= r and x > self.max2[v]:
        changed = self.cnt[v]                      # tag: exactly cnt elements
        self._apply_chmin(v, x)
        return changed
    self._push_down(v)
    mid = (lo + hi) // 2
    c = self.chmin_count(2*v, lo, mid, l, r, x) + self.chmin_count(2*v+1, mid+1, hi, l, r, x)
    self._merge(v)
    return c

This reuses the exact three-way structure — the count falls out of the tag case, demonstrating that the max1/max2/cnt augmentation is not just for sum but for any statistic about the affected elements.

These questions and the challenges span the whole topic. Solve the main challenge once with the skeleton, then from a blank file against a brute-force checker — the strict-max2 merge and the break condition are the two things you must get reflexively right.