Pattern Guide
Segment Tree Beats (Ji Driver)
"Range chmin/chmax in O(n log²n). Tags break only when strictly better value exists."
Segment Tree Beats (Ji Driver Segmentation) handles range operations like "set all elements > x to x" (range chmin) in O(n log²n). The key insight: only apply the operation to a subtree when the maximum changes; skip if it already satisfies the condition. Each node stores first and second maximum values. The tag propagates only when the new limit is strictly between them, ensuring each "break" is amortized efficiently.
17 min readdp problems →
Problems you can solve with this pattern
2 problems · click any to start solving
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);
}
}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);
}
}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
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