🗂️Data StructureAdvanced

Segment Tree Beats

Key Points

  • •
    Segment Tree Beats is a segment tree variant that supports range chmin/chmax (clamping) together with queries like range sum, min, and max in amortized logarithmic time.
  • •
    Each node stores the maximum, second maximum, and the count of the maximum (and symmetrically the minimum side) to decide when to stop, recurse, or apply a lazy-like partial update.
  • •
    For a range chmin, if x is at least the node's max we do nothing; if x is strictly between secon and max we can "beat" the node by lowering only the max entries; otherwise we must recurse to children.
  • •
    The key invariant is that second_ and second_ at every node, which bounds how often an element can be "beaten" before it stops propagating.
  • •
    Amortized complexity per operation is typically O(log n) to O(lo n), depending on which mix of operations you support and value distribution.
  • •
    Segment Tree Beats excels at problems involving range clamping (min or max) combined with range sum or extrema queries, common in high-rated competitive programming tasks.
  • •
    Unlike classic lazy propagation, we do not store a single tag for chmin/chmax; we partially apply updates only to the maximal (or minimal) elements tracked in each node.
  • •
    Careful push and pull procedures are essential to preserve invariants and achieve the amortized guarantees.

Prerequisites

  • →Segment trees (basic) — You need to understand how to represent range queries/updates in a binary tree over intervals and how to implement push/pull.
  • →Lazy propagation — Beats combines partial lazy application with recursion; knowing how and why to defer updates is essential.
  • →Big-O and amortized analysis — To reason about why operations are fast on average and how potentials bound total work.
  • →Max/min and frequency aggregation — Merging nodes relies on maintaining extrema, second extrema, and counts correctly.
  • →Integer overflow handling — Range sums can exceed 32-bit limits; use 64-bit types for correctness.

Detailed Explanation

Tap terms for definitions

01Overview

Segment Tree Beats is a specialized enhancement of the classic segment tree designed to handle range-clamping updates efficiently, such as setting every element a[i] in a range to min(a[i], x) (range chmin) or to max(a[i], x) (range chmax), while also supporting queries like range sum, range max, and range min. The naive approach of applying the clamp element-by-element is too slow, and standard lazy propagation does not directly handle chmin/chmax because these operations depend on current values in a non-linear way. The core idea of Segment Tree Beats is to maintain extra information at each node: the maximum value, the second maximum value, and the number of times the maximum occurs (and symmetrically for the minimum side if you also support chmax). With this metadata, an update can decide whether it can be applied to the entire node in one shot (by only changing the max elements), whether it is a no-op, or whether it must recurse into children. By ensuring a strict separation between max and second max (and similarly min versus second min), we can bound how much "work" can happen over a sequence of operations, leading to good amortized performance.

02Intuition & Analogies

Imagine you have stacks of boxes in segments along a line. A "range chmin to x" command means, in a given interval, trim every stack that is taller than x down to height x, but leave shorter stacks as-is. If you only knew the tallest stack in a combined region, you might think you have to check every stack to see who exceeds x. However, if you also know the second tallest stack, then you can tell whether only the tallest stacks will be affected. If x is still taller than the second tallest stack but shorter than the tallest, then only the current tallest stacks need trimming; the others are untouched. You can then instantly reduce only those tallest stacks without splitting the region further. If x is lower than or equal to the second tallest stack, trimming must affect more than just the currently tallest stacks, so you need to look more closely (recurse) into subregions. Over time, as you keep trimming, the tallest stacks in each region can only be cut down so many times before they fall below the second tallest stacks or the target x, after which future trims become no-ops or can be applied in bulk. This limits how much total work you do across many operations and is the heart of the amortized efficiency. The same picture holds in reverse for "range chmax to x": you raise only the currently smallest stacks up to x if x is between the minimum and the second minimum in that region.

03Formal Definition

We manage an array A[1..n] with operations like range chmin: for all i in [l, r], set A[i] := min(A[i], x), and range chmax: set A[i] := max(A[i], x). A Segment Tree Beats node v covering interval I stores: (1) max value over I, (2) second maximum over I, where or = - if not defined, (3) count of entries achieving , and similarly (4) min value , (5) second minimum , where or = + if not defined, (6) count of entries achieving , together with (7) sum of values in I and (8) optional lazy addition tag . For a range chmin with parameter x at node v: if x , we do nothing; if , we can "apply" at node v by decreasing only entries equal to to x, updating and accordingly without descending; else recurse to children. Symmetric rules apply for chmax with x relative to and . Node merges (pull) maintain invariants: = (, ), is the next candidate among child maxima, and counts how many equal maxima there are (similarly for the min side). Correctness follows by induction on intervals and the fact that we only alter entries known to be the unique global maxima (or minima) in the node.

04When to Use

Use Segment Tree Beats when you need to support range clamping updates (chmin or chmax) with queries such as sum, max, or min. Typical problems include maintaining an array of heights where operations cap or floor certain subranges, simulating processes that repeatedly cut peaks or fill valleys, or enforcing constraints like a[i] := min(a[i], x) over intervals while tracking total cost or final configuration. It's also effective when you interleave chmin/chmax with range additions, as long as you preserve the invariants and push order. Competitive programming tasks often ask for a data structure that handles: (1) range chmin/chmax, (2) range add, (3) range sum/min/max queries under up to 2e5 operations; Segment Tree Beats can solve these within time limits. If you only need range add/assign and queries, classical lazy propagation may be simpler. If you need arbitrary functions that are neither order-preserving nor piecewise monotone (e.g., set to a[i]^2), Segment Tree Beats likely won't apply; you need a different structure or offline/convex hull optimizations.

⚠️Common Mistakes

Common pitfalls include: (1) Forgetting to maintain second_max and second_min correctly when merging children; if smax equals max or smin equals min, invariants break and the decision logic for pruning fails. (2) Applying chmin at a node when x <= second_max; in this case you must recurse, or you'll corrupt non-maximum elements. (3) Not pushing constraints to children before recursing; when a parent’s max was previously lowered, you must ensure children’s max values are compatible (child.max <= parent.max) by applying the parent’s cap to any child that violates it. (4) Mixing add with chmin/chmax in the wrong push order; always push add first, then push max/min constraints so that comparisons are made on up-to-date values. (5) Using 32-bit integers for sums causing overflow; sums should be 64-bit (long long). (6) Forgetting that if x >= node.max for chmin (or x <= node.min for chmax), the update is a no-op and should return early. (7) Off-by-one boundaries in segment indices; stick to a consistent 0-based or 1-based convention. (8) Assuming worst-case per-operation time is always O(log n); the guarantee is amortized—some operations may descend deeper, but the structure ensures the total cost over many operations is bounded.

Key Formulas

Amortized per-operation time

Explanation: Each update or query takes logarithmic to polylogarithmic time on average over a sequence. The exact bound depends on the supported operations and how often nodes get "beaten" before becoming stable.

Range sum

Explanation: The sum over an interval is the total of all elements inside that range. Segment Tree Beats maintains this as a node aggregate and updates it when only maxima or minima change.

Max-side potential

Explanation: This potential measures the total "gap" between maximum and second maximum across nodes. A chmin that lowers only max elements strictly decreases P, bounding how many expensive descents can occur.

Min-side potential

Explanation: Analogous to the max-side potential, this is the total gap between the second minimum and the minimum. Range chmax operations decrease P', limiting total work.

Sum update under chmin

Explanation: When only the maximum entries are reduced to x, the node’s sum decreases by (ol - x) times the number of maximum entries. This is applied without descending to leaves.

Max/second-max merge

Explanation: When combining children, the parent’s max is the larger child max. The second max is the larger among the smaller child max and the children’s second maxima, preserving .

Min/second-min merge

Explanation: Similarly for minima, the parent’s min is the lesser child min, and the second min is chosen to remain strictly above the min.

Complexity Analysis

Let n be the array size and q the number of operations. A Segment Tree Beats maintains at each node the tuple (max, secon, coun) and, if supporting both chmin and chmax, also (min, secon, coun), plus sum and optional lazy add. A single operation descends like a typical segment tree O(log n), but may sometimes fail to finish at a node and must recurse because x <= secon (for chmin) or x >= secon (for chmax). The amortized bound arises from a potential argument: every time we perform a costly descent, we strictly reduce the gap between max and secon (or between secon and min) on at least one node by moving the max (or min) closer to the second extreme. Since values are finite, the total number of such gap-reductions across all nodes is bounded by O(n log V) or O(n log n) for typical integer ranges and merges along the tree. Hence, for range chmin/chmax with sum/extrema queries, the amortized time per operation is O(log n), and in more conservative analyses it is stated as O(lo n) to account for interactions and worst-case distributions. Queries like sum/min/max alone remain O(log n). Space usage is O(n) nodes (about 4n in a typical array-based implementation), each storing a constant amount of metadata, so O(n) total memory. When combined with range add, pushing order (add before min/max constraints) preserves the same asymptotic amortized bounds under standard assumptions.

Code Examples

Segment Tree Beats: range chmin + range sum/max (minimal version)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    long long sum;          // sum of the segment
6    long long mx;           // maximum in the segment
7    long long smax;         // second maximum (< mx), or -INF if not defined
8    int cmx;                // count of occurrences of mx
9    Node(long long v=LLONG_MIN) {
10        if (v==LLONG_MIN) { // default empty
11            sum = 0; mx = LLONG_MIN/4; smax = LLONG_MIN/4; cmx = 0;
12        } else {
13            sum = v; mx = v; smax = LLONG_MIN/4; cmx = 1;
14        }
15    }
16};
17
18struct SegTreeChminSumMax {
19    int n;
20    vector<Node> st;
21
22    SegTreeChminSumMax(const vector<long long>& a) {
23        n = (int)a.size();
24        st.resize(4*n);
25        build(1,0,n-1,a);
26    }
27
28    static Node merge(const Node& L, const Node& R){
29        Node res; res.sum = L.sum + R.sum;
30        if (L.mx == R.mx) {
31            res.mx = L.mx;
32            res.cmx = L.cmx + R.cmx;
33            res.smax = max(L.smax, R.smax);
34        } else if (L.mx > R.mx) {
35            res.mx = L.mx;
36            res.cmx = L.cmx;
37            res.smax = max(L.smax, R.mx);
38        } else {
39            res.mx = R.mx;
40            res.cmx = R.cmx;
41            res.smax = max(R.smax, L.mx);
42        }
43        return res;
44    }
45
46    void build(int p, int L, int R, const vector<long long>& a){
47        if (L==R){ st[p] = Node(a[L]); return; }
48        int M=(L+R)>>1; build(p<<1,L,M,a); build(p<<1|1,M+1,R,a);
49        st[p]=merge(st[p<<1],st[p<<1|1]);
50    }
51
52    // Apply chmin x to this node only on its maximum entries (safe if smax < x < mx)
53    void apply_chmin_node(int p, long long x){
54        if (x >= st[p].mx) return; // nothing to do
55        st[p].sum += (x - st[p].mx) * 1LL * st[p].cmx;
56        st[p].mx = x;
57        // smax unchanged because we only reduced the max values, and we ensured x > smax
58    }
59
60    // Push parent's max cap to children if they violate it
61    void push(int p){
62        int lc=p<<1, rc=p<<1|1;
63        long long cap = st[p].mx;
64        if (st[lc].mx > cap) apply_chmin_node(lc, cap);
65        if (st[rc].mx > cap) apply_chmin_node(rc, cap);
66    }
67
68    void range_chmin(int p,int L,int R,int ql,int qr,long long x){
69        if (qr<L || R<ql || x >= st[p].mx) return; // no overlap or no-op
70        if (ql<=L && R<=qr && x > st[p].smax){
71            apply_chmin_node(p, x);
72            return;
73        }
74        if (L==R) { // leaf
75            apply_chmin_node(p, x);
76            return;
77        }
78        push(p);
79        int M=(L+R)>>1;
80        range_chmin(p<<1, L, M, ql, qr, x);
81        range_chmin(p<<1|1, M+1, R, ql, qr, x);
82        st[p]=merge(st[p<<1],st[p<<1|1]);
83    }
84
85    Node query(int p,int L,int R,int ql,int qr){
86        if (qr<L || R<ql) return Node();
87        if (ql<=L && R<=qr) return st[p];
88        push(p);
89        int M=(L+R)>>1;
90        Node left = query(p<<1,L,M,ql,qr);
91        Node right= query(p<<1|1,M+1,R,ql,qr);
92        if (left.cmx==0) return right;
93        if (right.cmx==0) return left;
94        return merge(left,right);
95    }
96
97    // Public APIs
98    void chmin(int l,int r,long long x){ range_chmin(1,0,n-1,l,r,x); }
99    long long sum(int l,int r){ return query(1,0,n-1,l,r).sum; }
100    long long maxv(int l,int r){ return query(1,0,n-1,l,r).mx; }
101};
102
103int main(){
104    ios::sync_with_stdio(false); cin.tie(nullptr);
105    int n,q; cin>>n>>q;
106    vector<long long> a(n); for(int i=0;i<n;++i) cin>>a[i];
107    SegTreeChminSumMax st(a);
108    // Operations:
109    // 1 l r x : range chmin to x (0-indexed inclusive)
110    // 2 l r   : range sum
111    // 3 l r   : range max
112    while(q--){
113        int t; cin>>t; int l,r; cin>>l>>r;
114        if(t==1){ long long x; cin>>x; st.chmin(l,r,x); }
115        else if(t==2){ cout<<st.sum(l,r)<<"\n"; }
116        else { cout<<st.maxv(l,r)<<"\n"; }
117    }
118    return 0;
119}
120

This implementation supports range chmin with range sum and max queries. Each node maintains (sum, max, second max, count of max). An update applies in O(1) at a node if x is strictly between second max and max; otherwise it either returns (no-op) or recurses. The push step ensures children do not exceed the parent's current max cap.

Time: Amortized O(log n) to O(log^2 n) per update; O(log n) per querySpace: O(n)
Full Segment Tree Beats: range chmin, range chmax, range add, and queries (sum/min/max)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    long long sum;          // sum over the segment
6    long long mx, smax;     // maximum and second maximum
7    int cmx;                // count of maximum
8    long long mn, smin;     // minimum and second minimum
9    int cmn;                // count of minimum
10    long long add;          // lazy added to all elements in this segment
11    int len;                // segment length
12    Node(){
13        sum=0; mx=LLONG_MIN/4; smax=LLONG_MIN/4; cmx=0;
14        mn=LLONG_MAX/4; smin=LLONG_MAX/4; cmn=0; add=0; len=0;
15    }
16    Node(long long v, int l){
17        sum=v; mx=v; smax=LLONG_MIN/4; cmx=1;
18        mn=v; smin=LLONG_MAX/4; cmn=1; add=0; len=l;
19    }
20};
21
22struct SegTreeBeats {
23    int n; vector<Node> st;
24    SegTreeBeats(const vector<long long>& a){ n=a.size(); st.resize(4*n); build(1,0,n-1,a); }
25
26    static Node merge(const Node& L, const Node& R){
27        if (L.len==0) return R; if (R.len==0) return L;
28        Node res; res.len=L.len+R.len; res.sum=L.sum+R.sum; res.add=0;
29        // max side
30        if (L.mx==R.mx){ res.mx=L.mx; res.cmx=L.cmx+R.cmx; res.smax=max(L.smax,R.smax);} 
31        else if (L.mx>R.mx){ res.mx=L.mx; res.cmx=L.cmx; res.smax=max(L.smax,R.mx);} 
32        else { res.mx=R.mx; res.cmx=R.cmx; res.smax=max(R.smax,L.mx);} 
33        // min side
34        if (L.mn==R.mn){ res.mn=L.mn; res.cmn=L.cmn+R.cmn; res.smin=min(L.smin,R.smin);} 
35        else if (L.mn<R.mn){ res.mn=L.mn; res.cmn=L.cmn; res.smin=min(L.smin,R.mn);} 
36        else { res.mn=R.mn; res.cmn=R.cmn; res.smin=min(R.smin,L.mn);} 
37        return res;
38    }
39
40    void build(int p,int L,int R,const vector<long long>& a){
41        if (L==R){ st[p]=Node(a[L],1); return; }
42        int M=(L+R)>>1; build(p<<1,L,M,a); build(p<<1|1,M+1,R,a);
43        st[p]=merge(st[p<<1],st[p<<1|1]);
44    }
45
46    // Apply add to node p
47    void apply_add(int p, long long v){
48        st[p].sum += v * st[p].len;
49        st[p].mx += v; if (st[p].smax>LLONG_MIN/8) st[p].smax += v;
50        st[p].mn += v; if (st[p].smin<LLONG_MAX/8) st[p].smin += v;
51        st[p].add += v;
52    }
53
54    // Reduce only max elements to x at node p (require smax < x < mx)
55    void apply_chmin_max(int p, long long x){
56        if (x >= st[p].mx) return;
57        st[p].sum += (x - st[p].mx) * 1LL * st[p].cmx;
58        st[p].mx = x;
59        // smax unchanged, still < mx
60        if (st[p].mn > st[p].mx) st[p].mn = st[p].mx; // safe guard in equal-all case
61        if (st[p].smin > st[p].mx) st[p].smin = st[p].mx; // keep consistent upper bounds
62    }
63
64    // Raise only min elements to x at node p (require mn < x < smin)
65    void apply_chmax_min(int p, long long x){
66        if (x <= st[p].mn) return;
67        st[p].sum += (x - st[p].mn) * 1LL * st[p].cmn;
68        st[p].mn = x;
69        if (st[p].mx < st[p].mn) st[p].mx = st[p].mn;
70        if (st[p].smax < st[p].mn) st[p].smax = st[p].mn;
71    }
72
73    void push(int p){
74        if (st[p].len==1) { st[p].add=0; return; }
75        int lc=p<<1, rc=p<<1|1;
76        if (st[p].add!=0){ apply_add(lc, st[p].add); apply_add(rc, st[p].add); st[p].add=0; }
77        // Enforce parent's caps/floors on children
78        if (st[lc].mx > st[p].mx) apply_chmin_max(lc, st[p].mx);
79        if (st[rc].mx > st[p].mx) apply_chmin_max(rc, st[p].mx);
80        if (st[lc].mn < st[p].mn) apply_chmax_min(lc, st[p].mn);
81        if (st[rc].mn < st[p].mn) apply_chmax_min(rc, st[p].mn);
82    }
83
84    void range_add(int p,int L,int R,int ql,int qr,long long v){
85        if (qr<L || R<ql) return;
86        if (ql<=L && R<=qr){ apply_add(p,v); return; }
87        push(p);
88        int M=(L+R)>>1; range_add(p<<1,L,M,ql,qr,v); range_add(p<<1|1,M+1,R,ql,qr,v);
89        st[p]=merge(st[p<<1],st[p<<1|1]);
90    }
91
92    void range_chmin(int p,int L,int R,int ql,int qr,long long x){
93        if (qr<L || R<ql || x >= st[p].mx) return; // no overlap or no-op
94        if (ql<=L && R<=qr && x > st[p].smax){ apply_chmin_max(p,x); return; }
95        push(p);
96        int M=(L+R)>>1; range_chmin(p<<1,L,M,ql,qr,x); range_chmin(p<<1|1,M+1,R,ql,qr,x);
97        st[p]=merge(st[p<<1],st[p<<1|1]);
98    }
99
100    void range_chmax(int p,int L,int R,int ql,int qr,long long x){
101        if (qr<L || R<ql || x <= st[p].mn) return; // no overlap or no-op
102        if (ql<=L && R<=qr && x < st[p].smin){ apply_chmax_min(p,x); return; }
103        push(p);
104        int M=(L+R)>>1; range_chmax(p<<1,L,M,ql,qr,x); range_chmax(p<<1|1,M+1,R,ql,qr,x);
105        st[p]=merge(st[p<<1],st[p<<1|1]);
106    }
107
108    Node query(int p,int L,int R,int ql,int qr){
109        if (qr<L || R<ql) return Node();
110        if (ql<=L && R<=qr) return st[p];
111        push(p);
112        int M=(L+R)>>1; Node a=query(p<<1,L,M,ql,qr); Node b=query(p<<1|1,M+1,R,ql,qr);
113        return merge(a,b);
114    }
115
116    // Public API (0-indexed inclusive)
117    void add(int l,int r,long long v){ range_add(1,0,n-1,l,r,v); }
118    void chmin(int l,int r,long long x){ range_chmin(1,0,n-1,l,r,x); }
119    void chmax(int l,int r,long long x){ range_chmax(1,0,n-1,l,r,x); }
120    long long sum(int l,int r){ return query(1,0,n-1,l,r).sum; }
121    long long maxv(int l,int r){ return query(1,0,n-1,l,r).mx; }
122    long long minv(int l,int r){ return query(1,0,n-1,l,r).mn; }
123};
124
125int main(){
126    ios::sync_with_stdio(false); cin.tie(nullptr);
127    int n,q; cin>>n>>q; vector<long long> a(n); for(int i=0;i<n;++i) cin>>a[i];
128    SegTreeBeats st(a);
129    // Supported ops:
130    // 1 l r x : chmin [l,r] to x
131    // 2 l r x : chmax [l,r] to x
132    // 3 l r v : add v to [l,r]
133    // 4 l r   : sum [l,r]
134    // 5 l r   : max [l,r]
135    // 6 l r   : min [l,r]
136    while(q--){
137        int t; cin>>t; int l,r; cin>>l>>r;
138        if(t==1){ long long x; cin>>x; st.chmin(l,r,x); }
139        else if(t==2){ long long x; cin>>x; st.chmax(l,r,x); }
140        else if(t==3){ long long v; cin>>v; st.add(l,r,v); }
141        else if(t==4){ cout<<st.sum(l,r)<<"\n"; }
142        else if(t==5){ cout<<st.maxv(l,r)<<"\n"; }
143        else { cout<<st.minv(l,r)<<"\n"; }
144    }
145    return 0;
146}
147

This is a feature-complete Segment Tree Beats supporting range chmin, range chmax, range add, and queries for sum/min/max. The node stores both sides’ extrema and their second-best values with counts, plus a lazy add tag. The push order is critical: push add first, then enforce parent max/min constraints to children. Updates apply at a node if their threshold lies strictly between the extreme and the second extreme.

Time: Amortized O(log n) to O(log^2 n) per update; O(log n) per querySpace: O(n)
Application demo: enforcing bounds and tracking total cost
1#include <bits/stdc++.h>
2using namespace std;
3
4// Minimal beats for chmin + sum (reuse from Example 1)
5struct Node {
6    long long sum, mx, smax; int cmx; 
7    Node(long long v=LLONG_MIN){ if(v==LLONG_MIN){sum=0;mx=LLONG_MIN/4;smax=LLONG_MIN/4;cmx=0;} else {sum=v;mx=v;smax=LLONG_MIN/4;cmx=1;}}
8};
9struct SegTreeChminSumMax {
10    int n; vector<Node> st; SegTreeChminSumMax(const vector<long long>& a){ n=a.size(); st.resize(4*n); build(1,0,n-1,a);} 
11    static Node merge(const Node& L,const Node& R){ Node res; res.sum=L.sum+R.sum; if(L.mx==R.mx){res.mx=L.mx;res.cmx=L.cmx+R.cmx;res.smax=max(L.smax,R.smax);} else if(L.mx>R.mx){res.mx=L.mx;res.cmx=L.cmx;res.smax=max(L.smax,R.mx);} else {res.mx=R.mx;res.cmx=R.cmx;res.smax=max(R.smax,L.mx);} return res; }
12    void build(int p,int L,int R,const vector<long long>& a){ if(L==R){st[p]=Node(a[L]);return;} int M=(L+R)>>1; build(p<<1,L,M,a); build(p<<1|1,M+1,R,a); st[p]=merge(st[p<<1],st[p<<1|1]); }
13    void apply_chmin_node(int p,long long x){ if(x>=st[p].mx) return; st[p].sum += (x - st[p].mx) * 1LL * st[p].cmx; st[p].mx = x; }
14    void push(int p){ int lc=p<<1, rc=p<<1|1; long long cap = st[p].mx; if(st[lc].mx>cap) apply_chmin_node(lc,cap); if(st[rc].mx>cap) apply_chmin_node(rc,cap); }
15    void range_chmin(int p,int L,int R,int ql,int qr,long long x){ if(qr<L||R<ql||x>=st[p].mx) return; if(ql<=L&&R<=qr&&x>st[p].smax){ apply_chmin_node(p,x); return; } if(L==R){ apply_chmin_node(p,x); return; } push(p); int M=(L+R)>>1; range_chmin(p<<1,L,M,ql,qr,x); range_chmin(p<<1|1,M+1,R,ql,qr,x); st[p]=merge(st[p<<1],st[p<<1|1]); }
16    long long sum(int p,int L,int R,int ql,int qr){ if(qr<L||R<ql) return 0; if(ql<=L&&R<=qr) return st[p].sum; push(p); int M=(L+R)>>1; return sum(p<<1,L,M,ql,qr)+sum(p<<1|1,M+1,R,ql,qr); }
17    void chmin(int l,int r,long long x){ range_chmin(1,0,n-1,l,r,x);} long long sum(int l,int r){ return sum(1,0,n-1,l,r);} long long maxv(int l,int r){ // quick max via query merge
18        function<Node(int,int,int,int,int)> q=[&](int p,int L,int R,int ql,int qr){ if(qr<L||R<ql) return Node(); if(ql<=L&&R<=qr) return st[p]; push(p); int M=(L+R)>>1; Node a=q(p<<1,L,M,ql,qr), b=q(p<<1|1,M+1,R,ql,qr); if(a.cmx==0) return b; if(b.cmx==0) return a; return merge(a,b); }; return q(1,0,n-1,l,r).mx; }
19};
20
21int main(){
22    ios::sync_with_stdio(false); cin.tie(nullptr);
23    int n,q; cin>>n>>q; vector<long long> a(n); for(int i=0;i<n;++i) cin>>a[i];
24    SegTreeChminSumMax st(a);
25    // Problem: Given an upper bound U, repeatedly cap subranges to U and ask total sum.
26    // Commands:
27    // C l r U : cap [l,r] at U (a[i]=min(a[i],U))
28    // S l r   : print sum [l,r]
29    // M l r   : print max [l,r]
30    while(q--){
31        char op; cin>>op; int l,r; cin>>l>>r; if(op=='C'){ long long U; cin>>U; st.chmin(l,r,U);} else if(op=='S'){ cout<<st.sum(l,r)<<"\n";} else if(op=='M'){ cout<<st.maxv(l,r)<<"\n"; } }
32    return 0;
33}
34

This example shows a practical use: repeatedly enforce an upper bound (chmin) on ranges and query sums or maxima. It reuses the minimal beats structure. This kind of task appears frequently in contests about maintaining capped arrays or heights with cumulative totals.

Time: Amortized O(log n) to O(log^2 n) per cap; O(log n) per querySpace: O(n)