Segment Tree Beats

"Segment tree with min/max operations that break standard lazy. Range chmin/chmax, range sum queries in O(n log n)."

Deep Dive Tutorial

Standard lazy segment tree can't handle chmin/chmax (range "clamp") efficiently. Segment Tree Beats: each node stores max1 (largest), max2 (second largest), maxCnt (count of max elements). For chmin(l, r, v): if v >= max1, skip (nothing changes). If max2 < v < max1, apply: subtract the excess from max1 elements. If v <= max2, recurse into children. The "beats" condition: operation applies only if it strictly improves — preventing O(n) worst case per operation.

Segment Tree Beats for range chmin

class SegTreeBeats {
    constructor(arr) {
        const n = arr.length;
        this.n = n;
        this.max1 = new Array(4 * n).fill(-Infinity);
        this.max2 = new Array(4 * n).fill(-Infinity);
        this.maxCnt = new Array(4 * n).fill(0);
        this.sum = new Array(4 * n).fill(0);
        this.lazyMax = new Array(4 * n).fill(Infinity); // pending chmin
        this.build(arr, 1, 0, n - 1);
    }

    pushUp(t) {
        this.sum[t] = this.sum[2*t] + this.sum[2*t+1];
        if (this.max1[2*t] === this.max1[2*t+1]) {
            this.max1[t] = this.max1[2*t];
            this.maxCnt[t] = this.maxCnt[2*t] + this.maxCnt[2*t+1];
            this.max2[t] = Math.max(this.max2[2*t], this.max2[2*t+1]);
        } else if (this.max1[2*t] > this.max1[2*t+1]) {
            this.max1[t] = this.max1[2*t];
            this.maxCnt[t] = this.maxCnt[2*t];
            this.max2[t] = Math.max(this.max2[2*t], this.max1[2*t+1]);
        } else {
            this.max1[t] = this.max1[2*t+1];
            this.maxCnt[t] = this.maxCnt[2*t+1];
            this.max2[t] = Math.max(this.max1[2*t], this.max2[2*t+1]);
        }
    }

    applyMax(t, v) { // apply chmin(v): set max to min(max, v)
        if (v >= this.max1[t]) return;
        this.sum[t] -= (this.max1[t] - v) * this.maxCnt[t];
        this.max1[t] = v;
        this.lazyMax[t] = v;
    }

    pushDown(t) {
        if (this.lazyMax[t] < Infinity) {
            this.applyMax(2*t, this.lazyMax[t]);
            this.applyMax(2*t+1, this.lazyMax[t]);
            this.lazyMax[t] = Infinity;
        }
    }

    chmin(l, r, v, t = 1, tl = 0, tr = this.n - 1) {
        if (l > tr || r < tl || v >= this.max1[t]) return;
        if (l <= tl && tr <= r && v > this.max2[t]) { this.applyMax(t, v); return; }
        this.pushDown(t);
        const mid = (tl + tr) >> 1;
        this.chmin(l, r, v, 2*t, tl, mid);
        this.chmin(l, r, v, 2*t+1, mid+1, tr);
        this.pushUp(t);
    }

    query(l, r, t = 1, tl = 0, tr = this.n - 1) {
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return this.sum[t];
        this.pushDown(t);
        const mid = (tl + tr) >> 1;
        return this.query(l, r, 2*t, tl, mid) + this.query(l, r, 2*t+1, mid+1, tr);
    }
}

Worked Problems

Range Chmin/Chmax Sum Query

Hard

Solve ↗

The Number of Weak Characters in the Game

Medium

Solve ↗

flame

Segment Tree Beats key invariant:
Each node stores: max1 (max value), max2 (strict 2nd max), maxCnt (count of max elements).

chmin(v) rule:
- v >= max1: no change, skip
- max2 < v < max1: apply to this node (only max elements change)
- v <= max2: recurse into children

Amortized analysis: Each "break" (where we recurse past the check) eliminates a potential (reduces the number of distinct maximums). Total breaks = O(n log²n).

Operations supported:
- Range chmin: assign min(arr[i], v) for i in [l,r]
- Range chmax: symmetric
- Range sum query
- Range max/min query

← All Patterns