Segment Tree Beats

A lazy segment tree extended to handle updates that cannot be applied to a whole node in $O(1)$ — most famously chmin (range “set every element to $\min (a_i,x)$”).

The problem

Ordinary lazy propagation requires a tag that transforms a node’s aggregate in $O(1)$. For chmin(l, r, x), knowing only a node’s sum and range length is not enough — the new sum depends on how many elements exceed $x$ and by how much.

The fix: store more, and recurse when in doubt

Each node keeps:

• max1 — the maximum,
• max2 — the strict second maximum ($-\infty$ if all equal),
• cnt — how many elements equal max1,
• sum.

To apply chmin(x) at a node:

Case	Action
$x\ge max1$	nothing changes — return
$max2<x<max1$	only the maximums change: sum -= (max1 - x) * cnt; max1 = x; — $O(1)$, tag it
$x\le max2$	ambiguous — recurse into both children, then pull up

The third case is the “beats” part: recursion is allowed, and the amortized analysis shows it does not happen often.

void applyMin(int node, long long x) {
    if (x >= mx1[node]) return;
    sum[node] -= (mx1[node] - x) * cntMax[node];
    mx1[node] = x;
}
void update(int node, int l, int r, int ql, int qr, long long x) {
    if (qr < l || r < ql || x >= mx1[node]) return;            // case 1: prune
    if (ql <= l && r <= qr && mx2[node] < x) { applyMin(node, x); return; }  // case 2
    push(node);                                                 // case 3: recurse
    int m = (l + r) / 2;
    update(2*node, l, m, ql, qr, x);
    update(2*node+1, m+1, r, ql, qr, x);
    pull(node);
}

The complexity argument

Define a potential $\Phi ={\sum }_{\text{nodes}}(\text{number of distinct values in that node’s range})$. Initially $\Phi =O(n\log n)$.

• A chmin that hits case 2 merges two distinct values into one, decreasing $\Phi$.
• Each recursion in case 3 is paid for by a corresponding decrease.

Total: $O((n+q){\log }^{2}n)$ amortized for chmin plus range sum. With only chmin and range max (no sum), it improves to $O((n+q)\log n)$.

What it supports

Update	Query	Complexity
chmin / chmax	sum, max, min	$O({\log }^{2}n)$ am.
chmin + range add	sum, max	$O({\log }^{2}n)$ am.
chmin + chmax + add	sum, max, min	$O({\log }^{3}n)$ am.
range assign	anything	$O(\log n)$ — ordinary lazy
”add to all $a_i$ divisible by $d$“	sum	possible with more stored state
range $a_i\leftarrow \gcd (a_i,x)$	sum, gcd	works — values only shrink, bounded by $\log$ steps
range $a_i\leftarrow \lfloor a_i/x\rfloor$	sum	works — values shrink fast
range $a_i\leftarrow a_i^2$	sum	✘ — no bound on the potential

The general principle: beats works when the update makes values converge. Operations that spread values apart have no potential argument and no bound.

Combining with range add

Adding chmin and range add requires two lazy tags: one for the maximum elements and one for the rest, since they were shifted differently. This is the standard “Ji Driver Segment Tree” and it is genuinely fiddly — write it once, test it against a brute force, and keep it in a template file.

Simpler alternatives to check first

Situation	Simpler tool
Only range assign, no chmin	ordinary lazy segment tree
Range assign + random-ish data	”Chtholly tree” — an interval map in a std::map, $O(n\log \log n)$ expected
Only queries about the max, no sum	ordinary lazy segment tree with a max tag
$n$ small	sqrt decomposition with per-block sorted lists
Offline	sort by value and sweep

The Chtholly tree

For problems dominated by range assign, keep the array as a std::map<int, pair<int,int>> of maximal constant intervals. Assignment merges an entire range into one node; other operations iterate the (few) surviving intervals. On random data the number of intervals stays $O(\log n)$ amortized, giving very fast solutions in about 40 lines. It is not worst-case safe, so check the constraints.

See also: Lazy Propagation · Segment Tree · Sqrt Decomposition