Segment Tree Beats

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

huunguyen · Last updated 8, Tháng 4, 2026, 16:03

Segment Tree Beats (Ji Driver Segmentation) mở rộng lazy propagation để hỗ trợ range chmin ( $a [i] \leftarrow min (a [i], v)$ ) và range chmax — các phép cập nhật không thể lazy bình thường vì ảnh hưởng đến từng phần tử khác nhau.

Độ phức tạp: $O (N \log^{2} N)$ amortized cho $Q$ thao tác trên mảng $N$ phần tử.

Ứng dụng

Range chmin + range sum query.
Range chmax + range sum query.
Kết hợp: range add, range chmin, range chmax, range sum.

Ý tưởng

Tại mỗi node $[l, r]$ , lưu:

max1: giá trị lớn nhất.
max2: giá trị lớn thứ hai (nghiêm ngặt).
max_cnt: số lần xuất hiện của max1.
sum: tổng đoạn.

Khi range chmin $v$ trên node: nếu $v \geq max1$ , không làm gì. Nếu $max2 < v < max1$ , chỉ cập nhật max1 và sum (lazy). Nếu $v \leq max2$ , phải đi sâu xuống con.

Cài đặt

const int MAXN = 2e5 + 5;

struct Node {
    long long sum;
    int max1, max2, max_cnt;   // max lớn nhất, lớn thứ 2, đếm max lớn nhất
    int min1, min2, min_cnt;   // tương tự cho min
} t[4 * MAXN];

void push_up(int u) {
    t[u].sum = t[2*u].sum + t[2*u+1].sum;

    // Merge max
    if (t[2*u].max1 == t[2*u+1].max1) {
        t[u].max1 = t[2*u].max1;
        t[u].max_cnt = t[2*u].max_cnt + t[2*u+1].max_cnt;
        t[u].max2 = max(t[2*u].max2, t[2*u+1].max2);
    } else if (t[2*u].max1 > t[2*u+1].max1) {
        t[u].max1 = t[2*u].max1;
        t[u].max_cnt = t[2*u].max_cnt;
        t[u].max2 = max(t[2*u].max2, t[2*u+1].max1);
    } else {
        t[u].max1 = t[2*u+1].max1;
        t[u].max_cnt = t[2*u+1].max_cnt;
        t[u].max2 = max(t[2*u].max1, t[2*u+1].max2);
    }
    // Tương tự cho min (bỏ qua để ngắn gọn)
}

// Áp lazy chmin(v) vào node u (chỉ khi max2 < v < max1)
void push_chmin(int u, int v) {
    if (v >= t[u].max1) return;
    t[u].sum -= (long long)(t[u].max1 - v) * t[u].max_cnt;
    t[u].max1 = v;
    // Cập nhật min nếu cần (khi v < min1)
}

void push_down(int u) {
    push_chmin(2*u,   t[u].max1);
    push_chmin(2*u+1, t[u].max1);
    // push_chmax tương tự
}

void update_chmin(int u, int l, int r, int ql, int qr, int v) {
    if (ql > r || qr < l || v >= t[u].max1) return;
    if (ql <= l && r <= qr && v > t[u].max2) {
        push_chmin(u, v);
        return;
    }
    push_down(u);
    int mid = (l + r) / 2;
    update_chmin(2*u, l, mid, ql, qr, v);
    update_chmin(2*u+1, mid+1, r, ql, qr, v);
    push_up(u);
}

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

Các thao tác hỗ trợ

Thao tác	Điều kiện
Range chmin( $v$ )	Luôn hỗ trợ
Range chmax( $v$ )	Luôn hỗ trợ
Range add( $v$ )	Kết hợp với lazy add thông thường
Range sum query	Luôn hỗ trợ
Range max/min query	Luôn hỗ trợ

Độ phức tạp

$O (N \log^{2} N)$ amortized — phân tích potential: mỗi lần "phá vỡ" điều kiện lazy tốn $O (\log N)$ , tổng số lần phá vỡ là $O (N \log N)$ .

Khi nào dùng Segment Tree Beats?

Range chmin/chmax không thể xử lý bằng lazy thông thường.
Kết hợp nhiều loại cập nhật: add + chmin + chmax.
Bài toán "giới hạn giá trị" trên đoạn (ví dụ: clip tất cả phần tử vào $[l o, h i]$ ).

Bình luận

Không có bình luận tại thời điểm này.