Segment Tree Beats, in depth: range chmin with sums, the strict second maximum, tag order and the amortised bound

Why range chmin breaks lazy propagation

Recall what makes lazy propagation work, covered in detail in the segment tree deep dive. For an update to stop at a node that its range fully covers, two things must hold. First, the node's aggregate after the update must be computable from the aggregate before it plus the update parameter. Second, pending updates must compose, so a node can carry one tag that represents any sequence of them.

Range add satisfies both. Range chmin fails the first. Take a node covering [5, 9, 3, 9] with sum 26. After chmin with 6, the sum is 20; after chmin with 4 it is 15. Nothing in (sum, max) lets you compute either number.

The insight behind beats is to find a condition under which chmin does have a closed form, apply it only when the condition holds, and otherwise recurse. If x lies strictly between the node's largest value and its second largest value, then chmin changes exactly the elements equal to the maximum and nothing else. Every one of them becomes x, so the sum drops by (max - x) * count_of_max.

What each node stores

Each node stores five values:

• mx: the largest value in the range.
• se: the strict second largest value, meaning the largest value that is smaller than mx. If every element equals mx, it is minus infinity. Getting this wrong (storing the second element of a sorted list, which may equal the maximum) silently breaks the tag condition.
• cnt: how many elements equal mx.
• sm: the sum, which must be 64-bit in C++ or Java because chmin and add sequences push it well past 32-bit ranges on realistic inputs.
• add: a pending range-add tag, needed only if you support range add.

An update chmin(l, r, x) at a node then has three cases:

Note there is no separate chmin tag field. The node's own mx is the tag: when you later push down, any child whose maximum exceeds the parent's maximum must have been capped, so you clamp it to the parent's value. That is valid because the tag case only fires when every non-maximal element is below x, so in each child either the maximum is the one being capped or the child's whole range sits below the cap.

Worked example: one chmin, step by step

Take a = [5, 9, 3, 9, 7, 1, 8, 2], sum 44, and apply chmin(0, 7, 6). The root has maximum 9 (twice) and strict second maximum 8. Since 6 is not above 8, the tag case does not apply and we recurse.

The left half [5, 9, 3, 9] has maximum 9, count 2, second maximum 5. Now 5 < 6 < 9, so we tag: the sum drops by (9 - 6) * 2 = 6, from 26 to 20, and the maximum becomes 6. Its two children are not visited. The right half [7, 1, 8, 2] has maximum 8 and second maximum 7, which blocks the tag again, so we descend. [7, 1] tags (sum drops by 1) and [8, 2] tags (sum drops by 2). The final sum is 44 - 6 - 1 - 2 = 35, which matches the brute-force answer 5 + 6 + 3 + 6 + 6 + 1 + 6 + 2.

Notice what happened at the right half. Recursing there was not wasted. After the update its two children both have maximum 6 or below, and the right half's set of distinct values shrank from four to three. That shrinking is exactly what the complexity proof counts.

Tested implementation

The code below supports range chmin, range add, range sum and range max. It was run against a brute-force list on 400 random arrays with 200 mixed operations each, values allowed to go negative, before being published here.

NEG = float("-inf")

class Beats:
    def __init__(self, a):
        self.n = len(a)
        size = 4 * self.n
        self.mx = [0] * size     # largest value
        self.se = [NEG] * size   # strict second largest, -inf if none
        self.cnt = [0] * size    # count of elements equal to mx
        self.sm = [0] * size     # sum
        self.add = [0] * size    # pending add for children
        self.build(1, 0, self.n - 1, a)

    def pull(self, v):
        l, r = 2 * v, 2 * v + 1
        self.sm[v] = self.sm[l] + self.sm[r]
        if self.mx[l] == self.mx[r]:
            self.mx[v], self.cnt[v] = self.mx[l], self.cnt[l] + self.cnt[r]
            self.se[v] = max(self.se[l], self.se[r])
        elif self.mx[l] > self.mx[r]:
            self.mx[v], self.cnt[v] = self.mx[l], self.cnt[l]
            self.se[v] = max(self.se[l], self.mx[r])
        else:
            self.mx[v], self.cnt[v] = self.mx[r], self.cnt[r]
            self.se[v] = max(self.mx[l], self.se[r])

    def build(self, v, lo, hi, a):
        if lo == hi:
            self.mx[v], self.cnt[v], self.sm[v] = a[lo], 1, a[lo]
            return
        mid = (lo + hi) // 2
        self.build(2 * v, lo, mid, a)
        self.build(2 * v + 1, mid + 1, hi, a)
        self.pull(v)

    def apply_add(self, v, lo, hi, d):
        self.mx[v] += d
        if self.se[v] != NEG:
            self.se[v] += d
        self.sm[v] += d * (hi - lo + 1)
        self.add[v] += d

    def apply_chmin(self, v, x):          # caller guarantees se[v] < x
        if x >= self.mx[v]:
            return
        self.sm[v] -= (self.mx[v] - x) * self.cnt[v]
        self.mx[v] = x

    def push(self, v, lo, hi):
        mid = (lo + hi) // 2
        if self.add[v]:                   # add first: it shifts the cap too
            self.apply_add(2 * v, lo, mid, self.add[v])
            self.apply_add(2 * v + 1, mid + 1, hi, self.add[v])
            self.add[v] = 0
        self.apply_chmin(2 * v, self.mx[v])       # parent max is the cap
        self.apply_chmin(2 * v + 1, self.mx[v])

    def chmin(self, l, r, x, v=1, lo=0, hi=None):
        hi = self.n - 1 if hi is None else hi
        if r < lo or hi < l or self.mx[v] <= x:
            return                                # break
        if l <= lo and hi <= r and self.se[v] < x:
            self.apply_chmin(v, x)                # tag
            return
        self.push(v, lo, hi)                      # recurse
        mid = (lo + hi) // 2
        self.chmin(l, r, x, 2 * v, lo, mid)
        self.chmin(l, r, x, 2 * v + 1, mid + 1, hi)
        self.pull(v)

range_add, query_sum and query_max are the ordinary lazy segment tree routines: stop on full cover, otherwise push, recurse and pull. The one rule they share with chmin is that every descent goes through push, because a child's stored maximum may be stale until its parent's cap has been applied.

Push order, merges and sentinels

The most common bug is tag order in push. The pending add must reach the children before the cap does. The parent's mx already includes the add, so if you clamped the children against it first and then added, every capped child would end up d too high. Writing the push as "apply add, then clamp to the parent maximum" avoids keeping a separate chmin tag at all, and it also composes correctly across chmin, add, chmin sequences.

The second is the merge in pull. When both children share the maximum, the counts add and the second maximum is the larger of the two children's second maxima. When they differ, the smaller child's maximum becomes a candidate for the parent's second maximum. Forgetting that candidate makes se too small, the tag fires when it should not, and elements that sat between the true second maximum and x are never clamped.

Third, the sentinel: in C++ never add to LLONG_MIN; guard it as the code above does.

Why the extra recursion is bounded

Why is the extra recursion cheap? The intuitive argument for chmin plus sum, without add, goes like this. Define the potential of the tree as the total, over all nodes, of the number of distinct values in that node's range. Initially it is at most n per level, so O(n log n) overall. A chmin that recurses past a fully covered node does so only because the second maximum is at least x. After the update, the maximum and the second maximum both become x or merge into a single value, so the count of distinct values in that node drops by at least one. Each such extra visit therefore pays for itself by destroying one unit of potential, and the ordinary O(log n) visits per operation add only O(log n) new potential at most. Total cost: O((n + q) log n).

Range add breaks the simple version of this argument, because adding to part of a node's range can split one value into two and create potential. Ji's paper handles it with a finer potential over tag classes; the bound usually quoted for chmin combined with range add is O(log² n) amortised per operation. Treat that as the safe planning number.

Variants: chmax, modulo and historic values

Supporting chmax as well means mirroring every field: minimum, strict second minimum and its count. The fiddly part is a range that contains only one or two distinct values, where the maximum and minimum coincide. When you clamp the maximum, update the minimum if it was the same value, and vice versa.

Other problems that fit the same pattern include range modulo (a[i] %= m, recurse only where mx >= m; each element can shrink by at least half only O(log value) times), range square root on non-negative integers (every value reaches 0 or 1 within a handful of applications, after which the update is a no-op), and historic maximum queries, which keep the largest value each position has ever held.

Choosing between beats and the alternatives

Beats is not the only answer to range chmin. If queries can be answered offline, sorting the updates and using a simpler structure is often easier. Square-root decomposition supports chmin on blocks by keeping each block sorted, at O(sqrt n log n) per operation, which is slower but easier to get right under time pressure. A Fenwick tree cannot express chmin at all, because its updates must be invertible. And if you also need old versions of the array, persistent segment trees are the right base, though combining persistence with beats-style recursion multiplies memory quickly.

Failure modes

• Non-strict second maximum. Storing a second maximum that can equal the maximum makes the tag condition se < x false whenever there are duplicates, so you recurse to the leaves and the complexity becomes O(n) per update. The answers are still correct, only slow, which is why this bug survives correctness tests and shows up as a time limit.
• Clamping before adding on push. Wrong answers after any chmin that follows a pending add.
• Forgetting to push in queries. Reads a child's stale maximum and returns sums that ignore an earlier cap.
• 32-bit sums. Overflow with n around 2 * 10^5 and values near 10^9.
• Testing only narrow value ranges. Include negatives and wide ranges, and compare every query against a plain list.

What to do next

1. Implement chmin and sum only, with the strict second maximum, and test it against a brute-force list.
2. Add range add, put the add-before-clamp rule in push, and rerun the same random tests with mixed operations.
3. Instrument the number of nodes visited per update and confirm it stays small on random data; then try an adversarial input such as alternating chmin and add on overlapping ranges.
4. Extend to chmax by mirroring the fields, and test arrays with one and two distinct values first.
5. Revisit the segment tree deep dive to compare which updates need beats and which only need a lazy tag.