vii. Segment Tree Beats and Historic Values

Some updates can’t be applied to a whole node in $O(1)$: chmin needs to know how many elements exceed $x$, and mod x changes every element differently. Segment tree beats (Ji Ruyi, 2016) stores just enough to handle the easy cases in $O(1)$ and recurses in the hard ones, with a potential argument bounding the total recursion. Historic-value trees track “the maximum each element ever had” or “the sum over time” with tags that remember the best prefix of the update sequence.

Chmin, chmax, add with sum, max and min

Each node stores max, strict second max, count of max (and the same for min) plus the sum. chmin(x) on a node:

• $x\ge {\max }_1$: nothing to do;
• ${\max }_2<x<{\max }_1$: only the maximum elements change: sum -= (max1 - x) * cnt, max1 = x, tag it;
• $x\le {\max }_2$: recurse into the children.

struct Beats {
    static constexpr ll INF = LLONG_MAX / 4;
    struct N { ll mx1, mx2, mn1, mn2, cmx, cmn, sum, add; int len; };
    vector<N> t; int n;
    Beats(const vector<ll>& a) : n(sz(a)), t(4 * sz(a)) { build(1, 0, n, a); }
    void pull(int v) {
        N &x = t[v], &L = t[2 * v], &R = t[2 * v + 1];
        x.sum = L.sum + R.sum;
        if (L.mx1 == R.mx1) x.mx1 = L.mx1, x.cmx = L.cmx + R.cmx, x.mx2 = max(L.mx2, R.mx2);
        else if (L.mx1 > R.mx1) x.mx1 = L.mx1, x.cmx = L.cmx, x.mx2 = max(L.mx2, R.mx1);
        else x.mx1 = R.mx1, x.cmx = R.cmx, x.mx2 = max(L.mx1, R.mx2);
        if (L.mn1 == R.mn1) x.mn1 = L.mn1, x.cmn = L.cmn + R.cmn, x.mn2 = min(L.mn2, R.mn2);
        else if (L.mn1 < R.mn1) x.mn1 = L.mn1, x.cmn = L.cmn, x.mn2 = min(L.mn2, R.mn1);
        else x.mn1 = R.mn1, x.cmn = R.cmn, x.mn2 = min(L.mn1, R.mn2);
    }
    void build(int v, int l, int r, const vector<ll>& a) {
        t[v].len = r - l; t[v].add = 0;
        if (r - l == 1) { t[v] = {a[l], -INF, a[l], INF, 1, 1, a[l], 0, 1}; return; }
        int m = (l + r) / 2; build(2 * v, l, m, a); build(2 * v + 1, m, r, a); pull(v);
    }
    void applyAdd(int v, ll x) {
        N& a = t[v]; a.sum += x * a.len; a.mx1 += x; a.mn1 += x; a.add += x;
        if (a.mx2 != -INF) a.mx2 += x;
        if (a.mn2 != INF) a.mn2 += x;
    }
    void applyMin(int v, ll x) {                       // requires mx2 < x < mx1
        N& a = t[v]; if (a.mx1 <= x) return;
        a.sum -= (a.mx1 - x) * a.cmx;
        if (a.mn1 == a.mx1) a.mn1 = x;                 // node with one or two distinct values
        else if (a.mn2 == a.mx1) a.mn2 = x;
        a.mx1 = x;
    }
    void applyMax(int v, ll x) {                       // requires mn1 < x < mn2
        N& a = t[v]; if (a.mn1 >= x) return;
        a.sum += (x - a.mn1) * a.cmn;
        if (a.mx1 == a.mn1) a.mx1 = x;
        else if (a.mx2 == a.mn1) a.mx2 = x;
        a.mn1 = x;
    }
    void push(int v) {
        for (int c : {2 * v, 2 * v + 1}) {
            if (t[v].add) applyAdd(c, t[v].add);
            applyMin(c, t[v].mx1); applyMax(c, t[v].mn1);   // children never exceed the parent's extremes
        }
        t[v].add = 0;
    }
    void chmin(int v, int l, int r, int ql, int qr, ll x) {
        if (qr <= l || r <= ql || t[v].mx1 <= x) return;
        if (ql <= l && r <= qr && t[v].mx2 < x) { applyMin(v, x); return; }
        push(v); int m = (l + r) / 2;
        chmin(2 * v, l, m, ql, qr, x); chmin(2 * v + 1, m, r, ql, qr, x); pull(v);
    }
    void chmax(int v, int l, int r, int ql, int qr, ll x) {
        if (qr <= l || r <= ql || t[v].mn1 >= x) return;
        if (ql <= l && r <= qr && t[v].mn2 > x) { applyMax(v, x); return; }
        push(v); int m = (l + r) / 2;
        chmax(2 * v, l, m, ql, qr, x); chmax(2 * v + 1, m, r, ql, qr, x); pull(v);
    }
    void add(int v, int l, int r, int ql, int qr, ll x) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) { applyAdd(v, x); return; }
        push(v); int m = (l + r) / 2;
        add(2 * v, l, m, ql, qr, x); add(2 * v + 1, m, r, ql, qr, x); pull(v);
    }
    ll sum(int v, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) return 0;
        if (ql <= l && r <= qr) return t[v].sum;
        push(v); int m = (l + r) / 2;
        return sum(2 * v, l, m, ql, qr) + sum(2 * v + 1, m, r, ql, qr);
    }
};

Complexity: chmin/chmax with sum queries is $O((n+q)\log n)$ amortized without adds. With range adds it’s $O((n+q){\log }^{2}n)$. Potential: the number of distinct “max tags” across nodes; a recursion into a child happens only when two distinct values merge.

Proof: the three-case update is correct, including the $O(1)$ min/max-tracking patch

The three cases partition every query by comparing $x$ to $mx1,mx2$ (recall $mx2<mx1$ always), and are exhaustive. Case 1 ($x\ge mx1$) is correctly a no-op since $\min (a_i,x)=a_i$ for every $a_i\le mx1$. Case 3 ($x\le mx2$) makes no $O(1)$ claim, only recursing, so it cannot be wrong. Case 2 ($mx2<x<mx1$): every element $\le mx2$ is already $<x$ and untouched; the only elements that change are the $\mathrm{cmx}$ elements equal to $mx1$, each dropping by exactly $(mx1-x)$, so sum -= (mx1-x)*cmx is exact. The new $mx1$ is $x$, and $mx2$ is left alone correctly whenever the node has $\ge 3$ distinct values (the old $mx2$, being the strict second-largest, still sits strictly below the new $mx1=x$ since $mx2<x$). The min side needs patching only when the node has $\le 2$ distinct values, which is exactly when $mx1$ coincides with something the min-structure is tracking: if $mn1=mx1$ the whole range is one value, and that value (hence the range’s minimum too) is now $x$; if $mn2=mx1$ the range has exactly two distinct values $\{mn1,mx1\}$, and the min-side’s second-distinct value was $mx1$, now $x$. With $\ge 3$ distinct values, $mn2$ (the second-smallest of $\ge 3$ values) cannot equal $mx1$ (the largest), so neither branch fires and none is needed — the code’s two checks cover exactly these two patch cases and no others. $■$

Proof: amortized $O((n+q)\log n)$ without range add

For every node $v$ and at any instant, let $d(v)$ be the number of distinct array values currently occurring among the leaves in $v$‘s range, and let $\Phi ={\sum }_{v}d(v)$ over all $O(n)$ nodes.

Initial bound. $d(v)\le \mathrm{size}(v)$, and ${\sum }_v\mathrm{size}(v)=O(n\log n)$ ($O(n)$ per level, $O(\log n)$ levels), so ${\Phi }_0=O(n\log n)$.

Monotone. chmin/chmax never increase any $d(v)$: they only map some values down to a common value $x$, merging distinct classes, never splitting one value into two.

Case 2 doesn’t change $d(v)$ at that node. A direct $O(1)$ apply renames the $mx1$-class to $x$; since $mx2<x$, every other value stays strictly below the new maximum, so $v$‘s own distinct-value count is unchanged by its own application (nothing merges at $v$).

Every case-3 visit pays for itself. Let $v$ be any node visited in case 3 during some chmin(x) call ($mx2(v)\ge x$, so this is true regardless of whether $v$ started the cascade or is buried deep inside one). Let $V_x$ be the set of distinct values in $v$‘s range that are $\ge x$ before this call reaches $v$; $mx1(v),mx2(v)\in V_x$, so $|V_x|\ge 2$. By the time the recursive call on $v$‘s subtree finishes, every element whose value was in $V_x$ equals exactly $x$ (that is what chmin(\cdot,x) does to every value $\ge x$, wherever it is finally resolved), and every element $<x$ is untouched. So the $|V_x|\ge 2$ distinct values collapse into the single value $x$, and $d(v)$ drops by exactly $|V_x|-1\ge 1$. Charge the $O(1)$ overhead of visiting $v$ in case 3 (the dispatch, push, pull, and launching the two child calls) to this drop.

Summing the charges. $d(v)$ only decreases over the algorithm’s run and always stays $\ge 1$, so $v$ can be charged (visited in case 3) at most $d(v{)}_{\text{initial}}-1$ times in total, ever — consistent with the data structure itself: once $d(v)=1$, pull forces $mx2(v)=-\infty$ (by induction, since both children then also have $d=1$ and $mx2=-\infty$), so case 3 (which needs a finite $mx2(v)\ge x$) can never fire at $v$ again. Summed over all $O(n)$ nodes, the total number of case-3 visits across the entire run is at most ${\sum }_v(d(v{)}_{\text{initial}}-1)\le {\Phi }_0=O(n\log n)$.

Total cost. Each of the $q$ operations additionally does the ordinary $O(\log n)$ range-decomposition work any segment tree does (independent of beats), and $O(1)$ work per case-1/case-2 terminal; since the case-3 nodes visited during one call form a binary tree whose terminals are case-1/case-2 nodes, the terminal count is (case-3 count) $+1$ per cascade, so terminals are charged for free alongside the case-3 total. Grand total: $O(q\log n)$ (decomposition) $+O(n\log n)$ (case-3 visits, amortized over the whole run) $=O((n+q)\log n)$. $■$

With range add interleaved, applyMin/applyMax on a child during push can shift $mx2$ relative to the untouched part of the range in a way that breaks the clean ”$d(v)$ strictly drops” argument per visit (a pushed-down add can make a previously-equal value diverge again before the next chmin reaches it), costing an extra $O(\log n)$ factor; this interaction is Ji Ruyi’s original result and is cited here rather than re-derived.

Test against a brute force with random interleavings; the two-or-fewer-distinct-values edge cases (mn1 == mx1, mn2 == mx1) are where bugs hide.

Other “recurse while it matters” updates

Update	Stop condition	Bound
$a_i\leftarrow a_i\mathrm{mod}x$	node max $<x$	each change at least halves $a_i$: $O(\log A)$ changes per element
$a_i\leftarrow \lfloor \sqrt{a_i}\rfloor$	node max $\le 1$	$O(\log \log A)$ changes per element
$a_i\leftarrow \lfloor a_i/x\rfloor$ with range add	node max $-$ min small: convert to add when $\lfloor \max /x\rfloor -\max =\lfloor \min /x\rfloor -\min$	$O(\log A)$ per “distance” potential
$a_i\leftarrow \gcd (a_i,x)$	$x$ divisible by the node’s lcm (capped)	each change at least halves
$a_i\leftarrow a_i\&x$ / $a_i\mid x$	every element agrees on the affected bits: then it’s an add	$O(\log A)$ per bit flip

Total cost is $O((n+q)\log n\cdot (\text{changes per element}))$, plus sums of updates when combined with adds (count the potential carefully).

Proof: the per-element change bounds

Mod. If $a_i\ge x$ (otherwise mod x is a no-op), then $a_i\mathrm{mod}x<x\le a_i$; moreover $a_i\mathrm{mod}x\le a_i/2$ always: if $x\le a_i/2$ this holds since $a_i\mathrm{mod}x<x\le a_i/2$; if $x>a_i/2$ then $\lfloor a_i/x\rfloor =1$, so $a_i\mathrm{mod}x=a_i-x<a_i-a_i/2=a_i/2$. Either way $a_i$ at least halves, so it reaches $0$ after $O(\log A)$ changes.
Sqrt. Repeated $a_i\mapsto \lfloor \sqrt{a_i}\rfloor$ roughly halves ${\log }_2{a}_i$ each step (since $\log (\sqrt{a})=\frac{1}{2}\log a$ up to rounding), so $a_i$ reaches $\le 1$ after $O(\log \log A)$ changes.
Gcd. If $\gcd (a_i,x)<a_i$ (otherwise the update is a no-op), $\gcd (a_i,x)$ is a proper divisor of $a_i$, and the largest proper divisor of any integer $a_i>1$ is at most $a_i/2$ (its smallest prime factor is $\ge 2$), so $a_i$ at least halves per actual change, giving $O(\log A)$ changes.
AND/OR. Track, per node, the OR (for AND-updates) or AND (for OR-updates) of its range, used exactly as $mx1$ is used above: the stop condition is “this node already agrees with $x$ on every bit $x$ would change,” and the ambiguous/recurse condition is the negation. The same potential argument as the main beats proof applies with $\Phi ={\sum }_v\mathrm{popcount}(\text{node’s tracked aggregate})$ in place of ${\sum }_{v}d(v)$: ${\Phi }_0=O(n\log n\log A)$, and AND/OR never increases any bit’s count (AND only clears bits, OR only sets them, monotonically), so by the identical charging argument the total number of forced recursions is $O(n\log n\log A)$, i.e. $O(\log A)$ amortized changes per element. $■$

Historic maximum

Each element also tracks ${\text{hmax}}_i=\max$ over time of $a_i$. With range add only, a node’s tag is a pair (total add, best prefix of the adds since the last push). Applying a tag $(a,h)$ to a node: hmx = max(hmx, mx + h), mx += a, and the node’s own tag updates hadd = max(hadd, add + h), add += a.

With range assign too, a node that has been assigned since the last push only shifts its assigned value: tags become (add part, best add prefix) before the first assignment and (assigned value, best assigned value) after it. Push applies the add part first, then the assignment part. That’s Luogu P4314 (“CPU monitoring”).

Proof: the historic-maximum tag composition is correct

A pending tag $(a,h)$ on a node means: every leaf under it has had $+a$ applied to its current value since the last push, and at some point during that stretch (not necessarily now) its running value peaked at (current-value-before-this-stretch) $+h$ for the best prefix of the adds applied so far, with $h\ge a$ (the peak is at least as large as the final total, since $a$ is itself one valid prefix). Applying $(a,h)$ to a child with its own current max $\mathrm{mx}$ and historic max $\mathrm{hmx}$: the child’s value peaked, during the parent’s stretch, at $\mathrm{mx}+h$ (its value before the stretch, $\mathrm{mx}$, plus the best prefix $h$ of the adds applied since) — so $\mathrm{hmx}\leftarrow \max (\mathrm{hmx},\mathrm{mx}+h)$ correctly folds in this new peak without disturbing any higher peak from before the stretch. Then $\mathrm{mx}\leftarrow \mathrm{mx}+a$ applies the actual net change. Composing the child’s own pending tag $(a_c,h_c)$ with the incoming $(a,h)$: the combined stretch’s best prefix is the better of (child’s own best prefix $h_c$, reached before any of the parent’s stretch happened) or (child’s full stretch $a_c$ followed by the parent’s best prefix $h$, i.e. $a_c+h$) — so $h_c\leftarrow \max (h_c,a_c+h)$, matching hadd = max(hadd, add + h), and $a_c\leftarrow a_c+a$ matches add += a. Induction on the number of composed tags extends this to any pushed-down chain. $■$

Historic sum (sum over time of $a_i$, queried over ranges): keep the sum of $a$ and of the historic sums, plus a “time” tag: each tick adds the current sum to the historic sum. Lazy tags are affine in (value, history) and compose like matrices $\left(\begin{array}{cc}1& 0\\ t& 1\end{array}\right)$. This is the engine of offline “number of subarrays within $[l,r]$ with property” problems: sweep the right end, maintain for each left end a 0/1 or value, and accumulate history to count over all right ends.

Historic minimum, with chmin/chmax: combine beats with “best prefix” tags per class (max elements and others).