Wiki › Cấu trúc dữ liệu › Cây › Segment Tree Beats

Segment Tree Beats

huunguyen Updated Tháng sáu 2, 2026

Segment Tree Beats (còn gọi là Ji Driver Segment Tree, đặt theo tên tác giả Ruyi Ji) là một mở rộng mạnh mẽ của cây phân đoạn (segment tree) với lazy propagation, cho phép xử lý những phép cập nhật mà lazy thông thường không làm được, tiêu biểu là:

Range chmin: với mọi $i \in [l, r]$ , gán $a_{i} \leftarrow min (a_{i}, v)$ .
Range chmax: với mọi $i \in [l, r]$ , gán $a_{i} \leftarrow max (a_{i}, v)$ .

Kèm theo đó vẫn truy vấn được tổng đoạn (range sum), min/max đoạn, và có thể kết hợp với range add.

Vì sao chmin lại khó? Với lazy thông thường, một thẻ lazy "add $v$ " hay "gán $v$ " tác động đồng nhất lên cả đoạn, nên ta lưu một con số rồi đẩy xuống sau. Nhưng " $a_{i} \leftarrow min (a_{i}, v)$ " lại tác động khác nhau với từng phần tử: phần tử lớn hơn $v$ bị giảm về $v$ , phần tử nhỏ hơn $v$ giữ nguyên. Không có một con số chung nào mô tả được tác động này, nên lazy thường bó tay.

Độ phức tạp: $O ((N + Q) \log^{2} N)$ amortized cho $Q$ thao tác trên mảng $N$ phần tử — vẫn rất nhanh so với cập nhật từng phần tử $O (N Q)$ ngây thơ.

Ý tưởng / Trực giác

Quan sát chìa khoá: phép chmin $v$ trên một đoạn chỉ ảnh hưởng đến những phần tử lớn hơn $v$ . Nếu trong một node, tất cả các phần tử lớn hơn $v$ đều bằng nhau (đều bằng giá trị lớn nhất max1), thì phép chmin biến chúng đồng loạt thành $v$ — và đây lại là một tác động đồng nhất mà ta có thể lazy được!

Để khai thác điều đó, mỗi node $[l, r]$ lưu thêm thông tin về hai giá trị lớn nhất:

max1: giá trị lớn nhất trong đoạn.
max2: giá trị lớn thứ hai (nghiêm ngặt, tức $< max1$ ); nếu cả đoạn bằng nhau thì max2 $= - \infty$ .
cnt: số phần tử bằng max1.
sum: tổng đoạn.

Khi áp chmin $v$ lên một node, có ba trường hợp:

$v \geq max1$ : mọi phần tử đều $\leq v$ , phép chmin không thay đổi gì → dừng (cắt nhánh).
$max2 < v < max1$ : chỉ những phần tử bằng max1 mới bị ảnh hưởng, và chúng đều biến thành $v$ . Đây là tác động đồng nhất → cập nhật sum -= (max1 - v) * cnt, đặt max1 = v, đặt một thẻ lazy rồi dừng. Đây chính là "phép màu" của Segment Tree Beats.
$v \leq max2$ : phép chmin ảnh hưởng tới nhiều mức giá trị khác nhau, không thể lazy → đệ quy xuống cả hai con, rồi gộp lại (push_up).

Tính đúng đắn của trường hợp 2: vì $v > max2$ , không phần tử nào có giá trị nằm trong khoảng $(v, max1)$ . Chỉ các phần tử $= max1$ bị kẹp về $v$ , và sau đó $v$ vẫn $> max2$ nên max2 không đổi, cnt không đổi. Cấu trúc node được bảo toàn.

Điều khiến độ phức tạp vẫn tốt: trường hợp 3 ("phá vỡ", đệ quy sâu) xảy ra không quá nhiều lần. Trực giác là mỗi lần đệ quy sâu sẽ làm giảm số lượng các mức giá trị phân biệt trong cây; vì tổng số mức giá trị phân biệt ban đầu bị chặn, nên tổng chi phí của các lần "phá vỡ" được khấu trừ (amortized) về $O ((N + Q) \log^{2} N)$ .

Ví dụ chạy tay

Xét mảng (chỉ số 1..5):

 idx:   1    2    3    4    5
 val:  [ 5 ][ 5 ][ 2 ][ 4 ][ 5 ]

Cây phân đoạn (mỗi node ghi max1 / max2 / cnt / sum):

                 [1..5] 5/4/3/21
                /                \
        [1..3] 5/2/2/12        [4..5] 5/4/1/9
        /          \            /        \
  [1..2]5/-/2/10  [3]2/-/1/2  [4]4/-/1/4 [5]5/-/1/5
    /     \
 [1]5  [2]5

(- nghĩa là max2 $= - \infty$ vì node toàn giá trị bằng nhau.)

Thực hiện chmin( $v = 4$ ) trên cả đoạn [1..5]:

Bước 1 — node gốc [1..5]: max1=5, max2=4, cnt=3. Ta có $v = 4$ . Vì $v < max1 = 5$ nhưng $v = max2 = 4$ , không thoả $v > max2$ → rơi vào trường hợp 3, phải đệ quy xuống cả hai con.

gốc: max1=5, max2=4, v=4  ->  v <= max2  ->  ĐI SÂU

Bước 2 — con trái [1..3]: max1=5, max2=2, cnt=2. Ta có $max2 = 2 < v = 4 < max1 = 5$ → trường hợp 2 (phép màu)! Hai phần tử bằng 5 (idx 1, 2) đồng loạt thành 4.

[1..3]: sum 12 -> 12 - (5-4)*2 = 10 ;  max1: 5 -> 4 ;  đặt lazy chmin=4

Bước 3 — con phải [4..5]: max1=5, max2=4, cnt=1. Ta có $max2 = 4 = v$ , không thoả $v > max2$ → đệ quy.

Con [4]: giá trị 4, $v = 4 \geq max1$ → không đổi (trường hợp 1).
Con [5]: giá trị 5, $max2 = - \infty < 4 < 5$ → trường hợp 2: thành 4.
push_up([4..5]): sum $= 4 + 4 = 8$ , max1=4, cnt=2.

Bước 4 — push_up gốc: sum = 10 + 8 = 18, max1 = 4, ...

Mảng sau cập nhật:

 idx:   1    2    3    4    5
 val:  [ 4 ][ 4 ][ 2 ][ 4 ][ 4 ]      <- mọi giá trị bị kẹp xuống <= 4
 tổng = 18

Đúng như mong đợi: ban đầu tổng 21, ba số 5 bị giảm về 4 (mất $3 \times 1 = 3$ ), còn $18$ .

Cài đặt

Dưới đây là cài đặt đầy đủ hỗ trợ range chmin + range add + range sum + range max. (Range chmax đối xứng: lưu thêm min1, min2, min_cnt.)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 200005;
const ll INF = 1e18;

struct Node {
    ll sum;           // tổng đoạn
    ll max1, max2;    // giá trị lớn nhất, lớn thứ hai (nghiêm ngặt)
    ll cnt;           // số phần tử bằng max1
    ll lazy_add;      // lazy cộng dồn
} t[4 * MAXN];

int a[MAXN];

void push_up(int u) {
    int L = 2*u, R = 2*u+1;
    t[u].sum = t[L].sum + t[R].sum;
    if (t[L].max1 == t[R].max1) {
        t[u].max1 = t[L].max1;
        t[u].cnt  = t[L].cnt + t[R].cnt;
        t[u].max2 = max(t[L].max2, t[R].max2);
    } else if (t[L].max1 > t[R].max1) {
        t[u].max1 = t[L].max1;
        t[u].cnt  = t[L].cnt;
        t[u].max2 = max(t[L].max2, t[R].max1);   // max1 con phải có thể là max2
    } else {
        t[u].max1 = t[R].max1;
        t[u].cnt  = t[R].cnt;
        t[u].max2 = max(t[L].max1, t[R].max2);
    }
}

// Áp range add v vào node u
void apply_add(int u, int len, ll v) {
    t[u].sum  += v * len;
    t[u].max1 += v;
    if (t[u].max2 != -INF) t[u].max2 += v;  // không cộng vào -INF
    t[u].lazy_add += v;
}

// Áp chmin v vào node u — CHỈ gọi khi max2 < v < max1
void apply_chmin(int u, ll v) {
    if (v >= t[u].max1) return;
    t[u].sum -= (t[u].max1 - v) * t[u].cnt;  // chỉ các phần tử = max1 bị kẹp
    t[u].max1 = v;
}

void push_down(int u, int lenL, int lenR) {
    int L = 2*u, R = 2*u+1;
    // đẩy add trước
    if (t[u].lazy_add != 0) {
        apply_add(L, lenL, t[u].lazy_add);
        apply_add(R, lenR, t[u].lazy_add);
        t[u].lazy_add = 0;
    }
    // đẩy chmin: giá trị lớn nhất của cha là trần cho các con
    apply_chmin(L, t[u].max1);
    apply_chmin(R, t[u].max1);
}

void build(int u, int l, int r) {
    t[u].lazy_add = 0;
    if (l == r) {
        t[u].sum = t[u].max1 = a[l];
        t[u].max2 = -INF; t[u].cnt = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(2*u, l, mid);
    build(2*u+1, mid+1, r);
    push_up(u);
}

void update_add(int u, int l, int r, int ql, int qr, ll v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { apply_add(u, r - l + 1, v); return; }
    int mid = (l + r) / 2;
    push_down(u, mid - l + 1, r - mid);
    update_add(2*u, l, mid, ql, qr, v);
    update_add(2*u+1, mid+1, r, ql, qr, v);
    push_up(u);
}

void update_chmin(int u, int l, int r, int ql, int qr, ll v) {
    // điều kiện cắt: ngoài đoạn HOẶC v đã >= max1 (không ảnh hưởng)
    if (qr < l || r < ql || v >= t[u].max1) return;
    // điều kiện áp lazy: phủ trọn đoạn VÀ chỉ chạm vào tầng max1
    if (ql <= l && r <= qr && v > t[u].max2) {
        apply_chmin(u, v);
        return;
    }
    int mid = (l + r) / 2;
    push_down(u, mid - l + 1, r - mid);
    update_chmin(2*u, l, mid, ql, qr, v);
    update_chmin(2*u+1, mid+1, r, ql, qr, v);
    push_up(u);
}

ll query_sum(int u, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return t[u].sum;
    int mid = (l + r) / 2;
    push_down(u, mid - l + 1, r - mid);
    return query_sum(2*u, l, mid, ql, qr)
         + query_sum(2*u+1, mid+1, r, ql, qr);
}

ll query_max(int u, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return -INF;
    if (ql <= l && r <= qr) return t[u].max1;
    int mid = (l + r) / 2;
    push_down(u, mid - l + 1, r - mid);
    return max(query_max(2*u, l, mid, ql, qr),
               query_max(2*u+1, mid+1, r, ql, qr));
}

Hai dòng quan trọng nhất nằm trong update_chmin: điều kiện cắt nhánh v >= t[u].max1 (không có gì để làm) và điều kiện áp lazy v > t[u].max2 (chỉ tầng max1 bị chạm). Chính sự kết hợp của hai điều kiện này tạo ra độ phức tạp amortized tốt.

Độ phức tạp

Thao tác	Thời gian (amortized)
chmin / chmax / add / query	$O (\log^{2} N)$
Tổng $Q$ thao tác	$O ((N + Q) \log^{2} N)$
Bộ nhớ	$O (N)$

Vì sao $O (\log^{2} N)$ chứ không phải $O (\log N)$ ? Một thao tác chmin duyệt $O (\log N)$ node "biên" như segment tree thường. Nhưng tại các node đó, đôi khi điều kiện $v > max2$ không thoả và ta phải đệ quy sâu thêm (trường hợp 3). Phân tích hàm thế năng (potential) dựa trên "số mức giá trị phân biệt trên mỗi đường đi gốc–lá" cho thấy tổng số lần đệ quy sâu phụ trội trên toàn bộ $Q$ thao tác bị chặn bởi $O ((N + Q) \log N)$ bước, mỗi bước tốn $O (\log N)$ để đi tới, nên trung bình một thao tác là $O (\log^{2} N)$ . Khi chỉ có chmin (không có add), có thể chứng minh được cận chặt hơn $O ((N + Q) \log N)$ .

Bộ nhớ $O (N)$ : mảng $4 N$ node, mỗi node giữ một số hằng trường (sum, max1, max2, cnt, lazy_add).

⚠️ Lỗi thường gặp

Tràn số (overflow): sum của cả đoạn dễ vượt int. Với $N = 2 \cdot 10^{5}$ , $a_{i} \leq 10^{9}$ , tổng lên tới $2 \cdot 10^{14}$ → bắt buộc dùng long long. Phép (max1 - v) * cnt cũng phải tính trên long long, ép kiểu trước khi nhân nếu cần.
max2 = -INF bị cộng nhầm khi range add: khi áp apply_add, nếu cộng vô điều kiện vào max2, thì $- \infty$ sẽ biến thành một số hữu hạn rất âm và phá vỡ logic so sánh v > max2. Phải kiểm tra if (max2 != -INF) trước khi cộng. Đây là lỗi tinh vi, code vẫn chạy nhưng ra kết quả sai ở một số test.
Quên điều kiện cắt v >= max1 ở đầu update_chmin: nếu bỏ, thuật toán vẫn đúng nhưng mất hoàn toàn tính amortized — nó sẽ luôn đệ quy xuống lá và biến thành $O (N)$ mỗi truy vấn, dẫn tới TLE. Điều kiện cắt này không phải "tối ưu cho vui" mà là điều kiện bắt buộc để đạt độ phức tạp.
Sai thứ tự push_down giữa add và chmin: khi có cả hai loại lazy, phải đẩy add trước, chmin sau, vì thẻ chmin được biểu diễn ngầm qua max1 của cha sau khi đã cộng add. Đảo thứ tự sẽ áp trần chmin lên giá trị chưa cộng add, cho kết quả sai.
Lẫn lộn max2 "nghiêm ngặt" với "không nghiêm ngặt": max2 phải là giá trị lớn nhất thực sự nhỏ hơn max1. Nếu trong push_up bạn vô tình để max2 = max1 (ví dụ khi hai con bằng nhau mà lấy nhầm), thì điều kiện $v > max2$ gần như không bao giờ đúng → tụt về $O (N)$ .
Áp apply_chmin khi v <= max2: hàm apply_chmin chỉ đúng khi $v > max2$ (chỉ tầng max1 bị chạm). Gọi nó ở trạng thái $v \leq max2$ sẽ cập nhật sum sai vì còn nhiều phần tử khác cũng cần bị kẹp. Luôn để update_chmin kiểm tra v > t[u].max2 trước.

Biến thể / Mở rộng

Range chmax + range min query: đối xứng hoàn toàn, lưu thêm min1, min2, min_cnt.
Kết hợp đủ bộ: add + chmin + chmax + sum/min/max trong cùng một cây (cần đồng thời cả hai bộ trường max và min, push_down cẩn thận theo thứ tự add → chmin → chmax).
"Khistoric max" (lịch sử giá trị lớn nhất): mỗi vị trí lưu thêm giá trị lớn nhất từng đạt được qua thời gian — một dạng STB nâng cao dùng trong các bài như "Picture" / "max_v history".
Liên hệ: STB là phần mở rộng của Cây phân đoạn (Segment Tree) và [lazy propagation]. Nếu chưa nắm vững lazy propagation, hãy học nó trước.

Bài tập luyện

Lưu ý: pool CTOJ hiện chưa có bài thuần range chmin/chmax (Segment Tree Beats đúng nghĩa). Các bài dưới đây luyện nền tảng cây phân đoạn + lazy propagation + gộp node tuỳ biến — chính những kỹ năng mà Segment Tree Beats xây dựng lên. Hãy làm chắc chúng trước khi cài STB.

Đếm Kiện Cỏ (haybales15) — (Advanced) Range add + range min + range sum bằng lazy propagation — đây chính là cấu trúc nền mà STB mở rộng; làm bài này để nắm vững cách phối hợp nhiều lazy và truy vấn tổng/min trên cùng một cây.
Marathon (marathong) — (Veteran) Cây phân đoạn với phép gộp node tuỳ biến (giữ thông tin tổng đoạn và mức tiết kiệm lớn nhất khi bỏ một điểm) — luyện đúng tư duy "mỗi node lưu nhiều đại lượng phụ" như max1/max2/cnt trong STB.
Sắp Xếp Chỗ Ngồi (seating) — (Veteran) Cây phân đoạn lưu độ dài đoạn trống dài nhất (prefix/suffix/best) và cập nhật theo đoạn — rèn kỹ năng push_up gộp thông tin biên trái/phải, tiền đề cho việc gộp max1/max2 chính xác trong STB.