Khóa học CTDL và GT

Bài 30.5. Bài tập tổng hợp về Segment Tree

Chào mừng bạn đến với bài viết chuyên sâu về Segment Tree - một cấu trúc dữ liệu cực kỳ mạnh mẽ và linh hoạt, được sử dụng rộng rãi để giải quyết hiệu quả các bài toán liên quan đến truy vấn (query) và cập nhật (update) trên các phạm vi (range) của một mảng hoặc dãy số.

Nếu bạn đã nắm vững kiến thức cơ bản về Segment Tree (cách xây dựng, truy vấn điểm/phạm vi, cập nhật điểm), thì bài viết này sẽ đưa bạn đến những ứng dụng thực tế và các biến thể phức tạp hơn thông qua các bài tập minh họa cụ thể. Chúng ta sẽ cùng nhau đi sâu vào cách áp dụng sức mạnh của Segment Tree để giải quyết những thử thách thú vị.

Nhắc Lại Ngắn Gọn về Segment Tree

Segment Tree hoạt động dựa trên nguyên tắc chia để trị (Divide and Conquer). Nó biểu diễn một mảng dưới dạng một cây nhị phân, trong đó mỗi node trên cây chịu trách nhiệm quản lý một đoạn con (segment) của mảng gốc.

• Node gốc (root) quản lý toàn bộ mảng [0, N-1].
• Mỗi node con (child) quản lý một nửa đoạn của node cha. Node con trái quản lý nửa đầu, node con phải quản lý nửa sau.
• Node lá (leaf node) tương ứng với một phần tử duy nhất trong mảng gốc.

Thông tin lưu trữ tại mỗi node phụ thuộc vào bài toán cụ thể (ví dụ: tổng các phần tử, giá trị nhỏ nhất, giá trị lớn nhất, v.v., trong đoạn nó quản lý). Thông tin này tại node cha được tổng hợp từ thông tin của các node con.

Các thao tác cơ bản:

1. Xây dựng cây (Build): Tạo cây từ mảng ban đầu, đi từ lá lên gốc, tổng hợp thông tin tại mỗi node.
2. Cập nhật điểm (Point Update): Thay đổi giá trị của một phần tử trong mảng, sau đó cập nhật lại thông tin tại các node trên đường đi từ lá tương ứng lên gốc.
3. Truy vấn phạm vi (Range Query): Tính toán thông tin cần thiết trên một phạm vi [l, r] cho trước bằng cách kết hợp thông tin từ các node quản lý các đoạn con nằm hoàn toàn trong [l, r].

Cả ba thao tác này đều có độ phức tạp thời gian là O(log N), nơi N là kích thước mảng gốc. Đây chính là lợi thế vượt trội so với các thao tác O(N) trên mảng thông thường khi xử lý nhiều truy vấn/cập nhật liên tiếp.

Bây giờ, hãy cùng áp dụng kiến thức này vào các bài tập cụ thể!

Bài Tập 1: Truy Vấn Tổng trên Phạm Vi và Cập Nhật Điểm

Đây là bài toán kinh điển và cơ bản nhất của Segment Tree, nhưng là nền tảng vững chắc cho mọi bài toán phức tạp hơn.

Đề bài: Cho một mảng A gồm N phần tử. Hỗ trợ hai loại thao tác:

1. update index value: Cập nhật giá trị của phần tử tại chỉ số index thành value.
2. query l r: Tính tổng các phần tử trong mảng từ chỉ số l đến r (bao gồm cả l và r).

Giải pháp: Chúng ta sẽ xây dựng một Segment Tree nơi mỗi node lưu trữ tổng của đoạn con mà nó quản lý.

• Node state: Mỗi node lưu sum của đoạn [tl, tr].
• Combine operation: Tổng của đoạn [tl, tr] là tổng của đoạn [tl, tm] cộng tổng của đoạn [tm+1, tr], nơi tm là điểm giữa (tl+tr)/2.
• Build: Đệ quy từ gốc. Nếu là lá, lưu giá trị của phần tử tương ứng. Ngược lại, đệ quy xây dựng cây con trái và phải, sau đó tổng hợp kết quả.
• Update (Point): Đệ quy từ gốc. Tìm đến node lá tương ứng với chỉ số cần cập nhật. Thay đổi giá trị tại lá. Sau đó, đi ngược lên gốc, cập nhật lại tổng tại mỗi node bằng cách tổng hợp từ con.
• Query (Range): Đệ quy từ gốc.
  • Nếu đoạn của node [tl, tr] nằm hoàn toàn ngoài phạm vi truy vấn [l, r], trả về 0 (không đóng góp vào tổng).
  • Nếu đoạn của node [tl, tr] nằm hoàn toàn trong phạm vi truy vấn [l, r], trả về giá trị sum đã lưu trữ tại node này.
  • Nếu đoạn của node [tl, tr] một phần nằm trong [l, r], chia đoạn thành hai nửa và đệ quy xuống cây con trái và phải. Kết quả truy vấn là tổng kết quả từ hai cây con.

Code C++:

#include <iostream>
#include <vector>
#include <numeric> // for std::accumulate (optional, for initial sum)

// Kích thước mảng tối đa. Segment Tree cần khoảng 4*N không gian.
const int MAXN = 100005;
int arr[MAXN]; // Mảng gốc
long long tree[4 * MAXN]; // Mảng biểu diễn Segment Tree. long long cho tổng lớn.

// Hàm xây dựng cây Segment Tree
// v: chỉ số node hiện tại trong mảng tree[]
// tl, tr: đoạn con mà node v quản lý (chỉ số trong mảng arr[])
void build(int v, int tl, int tr) {
    if (tl == tr) {
        // Node lá: lưu giá trị của phần tử tương ứng
        tree[v] = arr[tl];
    } else {
        // Node nội bộ: đệ quy xây dựng cây con
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);         // Xây dựng cây con trái
        build(2 * v + 1, tm + 1, tr); // Xây dựng cây con phải
        // Tổng hợp kết quả từ con: tổng của node cha = tổng con trái + tổng con phải
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

// Hàm cập nhật giá trị tại một điểm trong mảng
// v: chỉ số node hiện tại
// tl, tr: đoạn con mà node v quản lý
// pos: chỉ số cần cập nhật trong mảng arr[]
// new_val: giá trị mới
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        // Đến node lá tương ứng, cập nhật giá trị
        tree[v] = new_val;
    } else {
        // Đệ quy tìm đến node lá
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            // Đi sang cây con trái nếu pos nằm trong đoạn [tl, tm]
            update(2 * v, tl, tm, pos, new_val);
        } else {
            // Đi sang cây con phải nếu pos nằm trong đoạn [tm+1, tr]
            update(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        // Sau khi đệ quy xong, cập nhật lại tổng tại node hiện tại
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

// Hàm truy vấn tổng trên một phạm vi [l, r]
// v: chỉ số node hiện tại
// tl, tr: đoạn con mà node v quản lý
// l, r: phạm vi truy vấn cần tính tổng
long long query(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        // Phạm vi truy vấn không hợp lệ hoặc nằm ngoài đoạn của node, trả về 0
        return 0;
    }
    if (l == tl && r == tr) {
        // Đoạn của node [tl, tr] nằm hoàn toàn trong phạm vi truy vấn [l, r], trả về giá trị đã lưu
        return tree[v];
    }
    // Đoạn của node một phần nằm trong phạm vi truy vấn
    // Chia đoạn của node và đệ quy
    int tm = (tl + tr) / 2;
    // Truy vấn trên cây con trái: lấy phần giao của [l, r] với [tl, tm] -> [l, min(r, tm)]
    long long sum_left = query(2 * v, tl, tm, l, std::min(r, tm));
    // Truy vấn trên cây con phải: lấy phần giao của [l, r] với [tm+1, tr] -> [max(l, tm+1), r]
    long long sum_right = query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
    // Tổng kết quả từ hai cây con
    return sum_left + sum_right;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Kích thước mảng
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Xây dựng cây Segment Tree
    build(1, 0, n - 1);

    int q; // Số lượng truy vấn
    std::cin >> q;

    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            // Cập nhật
            int index, value;
            std::cin >> index >> value;
            // Giả sử chỉ số 0-based
            update(1, 0, n - 1, index, value);
        } else {
            // Truy vấn
            int l, r;
            std::cin >> l >> r;
            // Giả sử chỉ số 0-based
            std::cout << query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

Giải thích code:

• tree[4 * MAXN] đủ lớn để chứa cây. Node gốc là tree[1]. Con trái của node v là 2*v, con phải là 2*v+1.
• Hàm build(v, tl, tr): Xây dựng cây đệ quy. tl, tr là ranh giới đoạn hiện tại. Base case tl == tr là node lá. Đệ quy gọi cho con trái [tl, tm] và con phải [tm+1, tr], sau đó tree[v] tổng hợp từ tree[2*v] và tree[2*v+1].
• Hàm update(v, tl, tr, pos, new_val): Tìm đến lá pos. Nếu pos <= tm, nó ở cây con trái. Ngược lại, ở cây con phải. Sau khi cập nhật ở dưới, cập nhật lại node hiện tại.
• Hàm query(v, tl, tr, l, r):
  • l > r: Phạm vi truy vấn không hợp lệ (ví dụ: l=5, r=2).
  • l == tl && r == tr: Đoạn của node [tl, tr] khớp chính xác với phạm vi truy vấn [l, r]. Ta đã lưu trữ tổng cho đoạn này rồi, trả về tree[v].
  • Các trường hợp khác: Đoạn của node [tl, tr] giao với [l, r]. Ta cần truy vấn trên hai cây con. Phạm vi truy vấn cho cây con trái là giao của [l, r] và [tl, tm], tức là [l, min(r, tm)]. Tương tự, cho cây con phải là [max(l, tm+1), r]. Kết quả là tổng hai truy vấn đệ quy.

Bài Tập 2: Truy Vấn Giá Trị Nhỏ Nhất/Lớn Nhất trên Phạm Vi

Biến thể phổ biến khác là tìm giá trị nhỏ nhất (hoặc lớn nhất) trong một phạm vi.

Đề bài: Cho một mảng A gồm N phần tử. Hỗ trợ hai loại thao tác:

1. update index value: Cập nhật giá trị của phần tử tại chỉ số index thành value.
2. query l r: Tìm giá trị nhỏ nhất trong mảng từ chỉ số l đến r.

Giải pháp: Tương tự bài toán tổng, nhưng mỗi node sẽ lưu trữ giá trị nhỏ nhất của đoạn con nó quản lý.

• Node state: Mỗi node lưu min_val của đoạn [tl, tr].
• Combine operation: Giá trị nhỏ nhất của đoạn [tl, tr] là min(min_val của cây con trái, min_val của cây con phải).
• Build/Update (Point): Logic giống bài tổng, chỉ thay phép cộng bằng phép min.
• Query (Range): Tương tự bài tổng, chỉ thay phép cộng bằng phép min. Nếu đoạn của node nằm hoàn toàn ngoài phạm vi truy vấn, trả về một giá trị rất lớn (vô cực) để không ảnh hưởng đến kết quả min.

Code C++ (chỉ khác biệt so với bài tổng):

#include <iostream>
#include <vector>
#include <algorithm> // for std::min, std::max
#include <limits>    // for std::numeric_limits

const int MAXN = 100005;
int arr[MAXN]; // Mảng gốc
// Sử dụng std::numeric_limits<int>::max() làm giá trị "vô cực" cho min query
int tree_min[4 * MAXN];

// Hàm xây dựng cây Segment Tree cho MIN
void build_min(int v, int tl, int tr) {
    if (tl == tr) {
        tree_min[v] = arr[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_min(2 * v, tl, tm);
        build_min(2 * v + 1, tm + 1, tr);
        // Tổng hợp kết quả: min của node cha = min(min con trái, min con phải)
        tree_min[v] = std::min(tree_min[2 * v], tree_min[2 * v + 1]);
    }
}

// Hàm cập nhật giá trị tại một điểm cho MIN
void update_min(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree_min[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update_min(2 * v, tl, tm, pos, new_val);
        } else {
            update_min(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        tree_min[v] = std::min(tree_min[2 * v], tree_min[2 * v + 1]);
    }
}

// Hàm truy vấn giá trị nhỏ nhất trên phạm vi [l, r]
int query_min(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        // Phạm vi không hợp lệ hoặc nằm ngoài đoạn của node, trả về "vô cực" dương
        return std::numeric_limits<int>::max();
    }
    if (l == tl && r == tr) {
        // Đoạn của node nằm hoàn toàn trong phạm vi truy vấn
        return tree_min[v];
    }
    int tm = (tl + tr) / 2;
    // Truy vấn cây con trái
    int min_left = query_min(2 * v, tl, tm, l, std::min(r, tm));
    // Truy vấn cây con phải
    int min_right = query_min(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
    // Kết quả là min của hai kết quả con
    return std::min(min_left, min_right);
}

// Hàm tương tự cho MAX query, chỉ cần thay std::min bằng std::max
// và giá trị "vô cực" ban đầu bằng std::numeric_limits<int>::min()
// build_max, update_max, query_max
// ... (code tương tự với min, thay đổi tên hàm và phép toán)

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Ví dụ chỉ dùng MIN
    build_min(1, 0, n - 1);

    int q;
    std::cin >> q;

    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            // Cập nhật
            int index, value;
            std::cin >> index >> value;
            update_min(1, 0, n - 1, index, value);
        } else {
            // Truy vấn
            int l, r;
            std::cin >> l >> r;
            std::cout << query_min(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

Giải thích code:

• Sự khác biệt chính so với bài toán tổng là kiểu dữ liệu lưu trữ (int thay vì long long nếu giá trị không quá lớn) và phép toán tổng hợp (std::min thay vì +).
• Giá trị trả về khi đoạn của node nằm ngoài phạm vi truy vấn cũng thay đổi. Đối với min, ta trả về giá trị lớn nhất có thể (std::numeric_limits<int>::max()) để nó không làm ảnh hưởng đến kết quả min. Đối với max, ta sẽ trả về giá trị nhỏ nhất có thể (std::numeric_limits<int>::min()).

Bài Tập 3: Cập Nhật Phạm Vi với Lazy Propagation

Đây là một kĩ thuật nâng cao hơn, giải quyết hiệu quả bài toán khi cần thực hiện cập nhật trên toàn bộ một phạm vi thay vì chỉ một điểm đơn lẻ. Nếu không dùng Lazy Propagation, cập nhật một phạm vi [l, r] có thể tốn O(N) trong trường hợp xấu nhất (khi phạm vi bao gồm nhiều node lá), làm mất đi lợi thế O(log N).

Đề bài: Cho một mảng A gồm N phần tử. Hỗ trợ hai loại thao tác:

1. update l r value: Cộng thêm value vào tất cả các phần tử trong mảng từ chỉ số l đến r.
2. query l r: Tính tổng các phần tử trong mảng từ chỉ số l đến r.

Giải pháp: Lazy Propagation. Ý tưởng là hoãn việc áp dụng cập nhật xuống các node con cho đến khi thực sự cần truy vấn hoặc cập nhật sâu hơn vào các node đó.

• Node state: Mỗi node lưu sum của đoạn [tl, tr] và một giá trị lazy biểu thị phần cập nhật đang chờ xử lý cho đoạn này.
• Build: Tương tự bài tổng, lazy khởi tạo bằng 0.
• push Operation: Một hàm push(v, tl, tr) để áp dụng giá trị lazy tại node v xuống các node con:
  • Nếu lazy[v] khác 0:
    • Áp dụng lazy[v] vào sum[v] (đã được tính ở tầng trên, giờ cần đảm bảo sum[v] phản ánh đúng tất cả các cập nhật). Công thức: sum[v] += lazy[v] * (tr - tl + 1) (cộng lazy[v] cho mỗi phần tử trong đoạn dài tr - tl + 1).
    • Nếu v không phải node lá (tức là tl != tr):
      • Truyền giá trị lazy[v] xuống cây con trái và phải: lazy[2*v] += lazy[v], lazy[2*v+1] += lazy[v].
    • Reset lazy[v] = 0.
• Update (Range): update_range(v, tl, tr, l, r, value):
  • Luôn gọi push(v, tl, tr) đầu tiên để xử lý các cập nhật lazy đang chờ tại node hiện tại trước khi đệ quy hoặc sử dụng giá trị sum.
  • Nếu đoạn [tl, tr] nằm hoàn toàn ngoài phạm vi [l, r], không làm gì cả.
  • Nếu đoạn [tl, tr] nằm hoàn toàn trong phạm vi [l, r]: Áp dụng value trực tiếp lên node này bằng cách cộng value vào lazy[v] (đừng cập nhật sum[v] ngay, việc áp dụng lên sum[v] sẽ được thực hiện bởi chính lệnh push vừa gọi ở đầu hàm hoặc các lệnh push sau này).
  • Nếu đoạn [tl, tr] một phần nằm trong [l, r]: Đệ quy xuống cây con trái và phải. Sau khi đệ quy xong, cập nhật lại sum[v] bằng cách tổng hợp từ sum của con trái và con phải (lưu ý: sum của con trái/phải đã được cập nhật đúng nhờ các lệnh push và đệ quy).
• Query (Range): query_range(v, tl, tr, l, r):
  • Luôn gọi push(v, tl, tr) đầu tiên để đảm bảo giá trị sum tại node hiện tại phản ánh đúng tất cả các cập nhật lazy.
  • Nếu đoạn [tl, tr] nằm hoàn toàn ngoài phạm vi [l, r], trả về 0.
  • Nếu đoạn [tl, tr] nằm hoàn toàn trong phạm vi [l, r]: Trả về sum[v].
  • Nếu đoạn [tl, tr] một phần nằm trong [l, r]: Đệ quy xuống cây con trái và phải. Kết quả là tổng của hai truy vấn đệ quy.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 100005;
int arr[MAXN];
long long tree_lazy_sum[4 * MAXN]; // Lưu tổng
long long lazy[4 * MAXN];          // Lưu giá trị lazy

// Hàm "đẩy" giá trị lazy xuống các node con
// v: chỉ số node hiện tại
// tl, tr: đoạn con node v quản lý
void push(int v, int tl, int tr) {
    if (lazy[v] != 0) {
        // Áp dụng giá trị lazy vào tổng của node hiện tại
        // lazy[v] được cộng vào mỗi phần tử trong đoạn [tl, tr]
        tree_lazy_sum[v] += lazy[v] * (tr - tl + 1);

        // Nếu không phải node lá, truyền giá trị lazy xuống con
        if (tl != tr) {
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
        }

        // Reset lazy value tại node hiện tại
        lazy[v] = 0;
    }
}

// Hàm xây dựng cây (không cần push vì lazy ban đầu là 0)
void build_lazy_sum(int v, int tl, int tr) {
    lazy[v] = 0; // Khởi tạo lazy
    if (tl == tr) {
        tree_lazy_sum[v] = arr[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_lazy_sum(2 * v, tl, tm);
        build_lazy_sum(2 * v + 1, tm + 1, tr);
        tree_lazy_sum[v] = tree_lazy_sum[2 * v] + tree_lazy_sum[2 * v + 1];
    }
}

// Hàm cập nhật phạm vi [l, r] với giá trị add_val
// v: chỉ số node hiện tại
// tl, tr: đoạn con node v quản lý
// l, r: phạm vi cần cập nhật
// add_val: giá trị cần cộng thêm
void update_range_lazy(int v, int tl, int tr, int l, int r, int add_val) {
    // LUÔN gọi push trước
    push(v, tl, tr);

    if (l > r || tl > r || tr < l) {
        // Đoạn của node nằm hoàn toàn ngoài phạm vi cập nhật
        return;
    }
    if (l <= tl && tr <= r) {
        // Đoạn của node nằm hoàn toàn trong phạm vi cập nhật
        // Cộng giá trị vào lazy tại node này
        lazy[v] += add_val;
        // Áp dụng ngay lazy vừa thêm vào node hiện tại
        // Các node con sẽ nhận lazy này khi push được gọi cho chúng
        push(v, tl, tr);
        return;
    }

    // Đoạn của node một phần nằm trong phạm vi cập nhật
    int tm = (tl + tr) / 2;
    update_range_lazy(2 * v, tl, tm, l, r, add_val);         // Cập nhật cây con trái
    update_range_lazy(2 * v + 1, tm + 1, tr, l, r, add_val); // Cập nhật cây con phải
    // Sau khi cập nhật con, tổng của node cha = tổng con trái + tổng con phải
    tree_lazy_sum[v] = tree_lazy_sum[2 * v] + tree_lazy_sum[2 * v + 1];
}

// Hàm truy vấn tổng trên phạm vi [l, r] với Lazy Propagation
// v: chỉ số node hiện tại
// tl, tr: đoạn con node v quản lý
// l, r: phạm vi cần truy vấn
long long query_range_lazy(int v, int tl, int tr, int l, int r) {
    // LUÔN gọi push trước
    push(v, tl, tr);

    if (l > r || tl > r || tr < l) {
        // Đoạn của node nằm hoàn toàn ngoài phạm vi truy vấn
        return 0;
    }
    if (l <= tl && tr <= r) {
        // Đoạn của node nằm hoàn toàn trong phạm vi truy vấn
        return tree_lazy_sum[v];
    }

    // Đoạn của node một phần nằm trong phạm vi truy vấn
    int tm = (tl + tr) / 2;
    // Truy vấn cây con trái
    long long sum_left = query_range_lazy(2 * v, tl, tm, l, std::min(r, tm));
    // Truy vấn cây con phải
    long long sum_right = query_range_lazy(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
    // Tổng kết quả
    return sum_left + sum_right;
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build_lazy_sum(1, 0, n - 1);

    int q;
    std::cin >> q;

    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            // Cập nhật phạm vi
            int l, r, add_val;
            std::cin >> l >> r >> add_val;
            // Giả sử chỉ số 0-based
            update_range_lazy(1, 0, n - 1, l, r, add_val);
        } else {
            // Truy vấn phạm vi
            int l, r;
            std::cin >> l >> r;
            // Giả sử chỉ số 0-based
            std::cout << query_range_lazy(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

Giải thích code Lazy Propagation:

• Mảng lazy[4 * MAXN] được thêm vào để lưu giá trị cập nhật "đang chờ".
• Hàm push(v, tl, tr) là trái tim của Lazy Propagation. Nó kiểm tra nếu có lazy tại node v. Nếu có, nó áp dụng giá trị lazy này lên tree_lazy_sum[v]. Sau đó, nếu v không phải lá, nó truyền giá trị lazy xuống con và cuối cùng xóa lazy[v] bằng cách đặt về 0.
• Trong update_range_lazy và query_range_lazy, lệnh push(v, tl, tr) được gọi ngay ở đầu hàm. Điều này đảm bảo rằng khi ta xử lý node v hoặc đệ quy xuống con, mọi cập nhật "đang chờ" từ các tầng trên đã được xử lý.
• Trong update_range_lazy:
  • Nếu đoạn [tl, tr] nằm hoàn toàn trong [l, r], thay vì cập nhật từng phần tử, ta chỉ cần cộng thêm add_val vào lazy[v]. Lệnh push ngay sau đó sẽ áp dụng giá trị lazy này vào tree_lazy_sum[v].
  • Nếu chỉ giao một phần, ta đệ quy xuống con. Sau khi đệ quy, tree_lazy_sum[v] được cập nhật lại từ con như bình thường.
• Trong query_range_lazy:
  • Tương tự update, push được gọi đầu tiên.
  • Nếu đoạn [tl, tr] hoàn toàn trong [l, r], ta trả về tree_lazy_sum[v] (đã được đảm bảo là chính xác nhờ push).
  • Nếu chỉ giao một phần, đệ quy và tổng hợp kết quả từ con.

Lazy Propagation giúp giữ độ phức tạp của cả cập nhật phạm vi và truy vấn phạm vi ở mức O(log N). Nó là kỹ thuật quan trọng cho nhiều bài toán Segment Tree nâng cao.

Bài Tập 4: Truy Vấn Có Điều Kiện và Cấu Trúc Node Phức Tạp Hơn

Đôi khi, bài toán yêu cầu thông tin tại node không chỉ đơn giản là tổng, min, hay max. Cấu trúc node có thể cần lưu nhiều thông tin hơn để hỗ trợ truy vấn đặc biệt. Hãy xem xét một bài toán truy vấn tìm kiếm đầu tiên trong một phạm vi.

Đề bài: Cho một mảng A gồm N phần tử. Hỗ trợ hai loại thao tác:

1. update index value: Cập nhật giá trị của phần tử tại chỉ số index thành value.
2. find_first l r K: Tìm chỉ số nhỏ nhất i trong phạm vi [l, r] sao cho A[i] >= K. Nếu không có phần tử nào như vậy, trả về -1.

Giải pháp: Bài toán này không thể giải chỉ bằng cách kết hợp kết quả từ các node con như bài tổng hay min/max thông thường. Việc tìm "chỉ số đầu tiên" đòi hỏi một cách duyệt cây có thứ tự. Để làm được điều này hiệu quả, mỗi node cần lưu trữ thông tin đủ để quyết định liệu có cần duyệt sâu hơn vào cây con trái hay không. Đối với bài toán tìm phần tử >= K, thông tin hữu ích là giá trị lớn nhất trong đoạn của node.

• Node state: Mỗi node lưu max_val của đoạn [tl, tr].
• Combine operation: max_val của node cha là max(max_val của cây con trái, max_val của cây con phải).
• Build/Update (Point): Logic tương tự bài toán max, cập nhật max_val đi lên.
• Query (find_first): query_first(v, tl, tr, l, r, K):
  • Nếu đoạn [tl, tr] nằm hoàn toàn ngoài phạm vi truy vấn [l, r] HOẶC max_val tại node v nhỏ hơn K, thì không có phần tử nào >= K trong đoạn này nằm trong [l, r]. Trả về -1.
  • Nếu là node lá (tl == tr): Đây là phần tử đơn lẻ. Nó chắc chắn >= K (vì đã vượt qua điều kiện max_val >= K). Trả về chỉ số tl (hoặc tr).
  • Nếu không phải node lá: Ta cần tìm chỉ số nhỏ nhất. Ưu tiên tìm ở cây con trái trước.
    • Kiểm tra cây con trái (2*v): Nếu max_val của cây con trái >= K VÀ đoạn [tl, tm] (giao với [l, r]) có thể chứa kết quả (max(l, tl) <= min(r, tm)), đệ quy query_first trên cây con trái với phạm vi [l, r]. Nếu kết quả khác -1, trả về kết quả đó.
    • Nếu cây con trái không có kết quả (hoặc max_val < K): Đệ quy query_first trên cây con phải (2*v+1) với phạm vi [l, r]. Trả về kết quả từ cây con phải.

Code C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

const int MAXN = 100005;
int arr[MAXN];
int tree_max[4 * MAXN]; // Lưu giá trị lớn nhất

// Hàm xây dựng cây Segment Tree cho MAX
void build_max(int v, int tl, int tr) {
    if (tl == tr) {
        tree_max[v] = arr[tl];
    } else {
        int tm = (tl + tr) / 2;
        build_max(2 * v, tl, tm);
        build_max(2 * v + 1, tm + 1, tr);
        tree_max[v] = std::max(tree_max[2 * v], tree_max[2 * v + 1]);
    }
}

// Hàm cập nhật giá trị tại một điểm cho MAX
void update_max(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree_max[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update_max(2 * v, tl, tm, pos, new_val);
        } else {
            update_max(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        tree_max[v] = std::max(tree_max[2 * v], tree_max[2 * v + 1]);
    }
}

// Hàm truy vấn tìm chỉ số đầu tiên >= K trong phạm vi [l, r]
// v: chỉ số node hiện tại
// tl, tr: đoạn con node v quản lý
// l, r: phạm vi truy vấn
// K: giá trị ngưỡng
int query_first_geq(int v, int tl, int tr, int l, int r, int K) {
    // 1. Nếu đoạn của node nằm hoàn toàn ngoài phạm vi truy vấn [l, r]
    // 2. Hoặc giá trị lớn nhất trong đoạn của node nhỏ hơn K
    //    (nghĩa là không có phần tử nào >= K trong đoạn này)
    if (l > r || tl > r || tr < l || tree_max[v] < K) {
        return -1; // Không tìm thấy
    }

    // Nếu là node lá và thỏa mãn điều kiện >= K
    // (Điều kiện tree_max[v] >= K đã được kiểm tra ở trên)
    if (tl == tr) {
        return tl; // Trả về chỉ số
    }

    // Node nội bộ
    int tm = (tl + tr) / 2;

    // Ưu tiên tìm ở cây con trái
    // Chỉ đệ quy nếu cây con trái CÓ THỂ chứa kết quả (max_val >= K)
    // và có phần giao với phạm vi truy vấn [l, r]
    int res_left = -1;
    if (tree_max[2 * v] >= K) { // Tối ưu: Chỉ đệ quy nếu cây con trái có khả năng chứa kết quả
         res_left = query_first_geq(2 * v, tl, tm, l, r, K);
    }


    if (res_left != -1) {
        return res_left; // Nếu tìm thấy ở cây con trái, đó là chỉ số nhỏ nhất
    } else {
        // Nếu không tìm thấy ở cây con trái, tìm ở cây con phải
        // Chỉ đệ quy nếu cây con phải CÓ THỂ chứa kết quả (max_val >= K)
        if (tree_max[2 * v + 1] >= K) { // Tối ưu
            return query_first_geq(2 * v + 1, tm + 1, tr, l, r, K);
        } else {
             return -1; // Không tìm thấy ở cả hai con
        }
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    build_max(1, 0, n - 1);

    int q;
    std::cin >> q;

    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            // Cập nhật
            int index, value;
            std::cin >> index >> value;
            update_max(1, 0, n - 1, index, value);
        } else {
            // Truy vấn tìm đầu tiên >= K
            int l, r, K;
            std::cin >> l >> r >> K;
            std::cout << query_first_geq(1, 0, n - 1, l, r, K) << "\n";
        }
    }

    return 0;
}

Giải thích code query_first_geq:

• Hàm query_first_geq khác với các hàm query trước đó ở chỗ nó không chỉ đơn thuần kết hợp kết quả đệ quy. Nó có logic riêng để tìm kiếm.
• Điều kiện thoát đệ quy đầu tiên l > r || tl > r || tr < l || tree_max[v] < K kiểm tra xem đoạn hiện tại có thể chứa kết quả mong muốn hay không. Nếu không, trả về -1.
• Nếu là node lá tl == tr và đã vượt qua điều kiện trên, nghĩa là arr[tl] >= K, đây chính là phần tử đầu tiên (duy nhất) trong đoạn này, trả về chỉ số tl.
• Nếu là node nội bộ, ta ưu tiên tìm ở cây con trái trước (query_first_geq(2*v, tl, tm, l, r, K)). Nếu tìm thấy kết quả khác -1 ở cây con trái, đó chính là chỉ số nhỏ nhất cần tìm vì cây con trái biểu diễn đoạn bên trái hơn.
• Chỉ khi cây con trái không tìm thấy kết quả, ta mới tiếp tục tìm ở cây con phải (query_first_geq(2*v+1, tm+1, tr, l, r, K)).

Kỹ thuật này (duyệt có điều kiện) có thể mở rộng để tìm kiếm các phần tử theo các tiêu chí khác nhau, miễn là thông tin lưu trữ tại node đủ để ra quyết định duyệt nhánh nào trước.

Lời Khuyên Khi Giải Bài Tập Segment Tree Tổng Hợp

1. Xác định cấu trúc node: Câu hỏi quan trọng nhất là "Mỗi node Segment Tree cần lưu thông tin gì để giải quyết bài toán?". Đó có thể là tổng, min, max, cặp giá trị (min và max), số lượng, cờ trạng thái, v.v.
2. Định nghĩa phép tổng hợp: Làm thế nào để tính thông tin của node cha từ thông tin của các node con? (Ví dụ: sum = sum_left + sum_right, min = min(min_left, min_right)).
3. Xác định loại cập nhật: Cập nhật chỉ một điểm hay cả một phạm vi? Nếu là phạm vi, bạn có cần Lazy Propagation không?
4. Thiết kế hàm Query: Logic truy vấn có đơn giản là kết hợp kết quả đệ quy không, hay cần một logic tìm kiếm/duyệt cây có điều kiện (như bài tìm chỉ số đầu tiên)?
5. Kích thước mảng tree: Luôn dùng kích thước khoảng 4 * N cho an toàn.
6. Chỉ số: Cẩn thận với chỉ số 0-based hay 1-based của mảng gốc và Segment Tree. Nhất quán trong toàn bộ code.
7. Giá trị "vô cực": Khi tính min/max, sử dụng giá trị rất lớn/rất nhỏ (như từ <limits>) khi một đoạn nằm ngoài phạm vi truy vấn. Đối với tổng, giá trị là 0.
8. Lazy Propagation: Nhớ gọi hàm push trước khi xử lý node hiện tại hoặc đệ quy xuống con trong cả hàm update và query. Cẩn thận khi áp dụng giá trị lazy (cộng vào sum, truyền xuống con).

Bài tập ví dụ:

Số Nguyên Khác Nhau Trong Đoạn

Trong một dự án thủy lợi, FullHouse Dev được giao nhiệm vụ phân tích dữ liệu từ các cảm biến đo lường. Họ nhận được hai mảng số liệu và cần xác định số lượng giá trị khác nhau trong các đoạn được chỉ định.

Bài toán

Cho hai mảng \(A\) và \(B\), mỗi mảng có độ dài \(N\). Tiếp theo là \(Q\) truy vấn, mỗi truy vấn gồm hai cặp chỉ số xác định một đoạn trong mảng \(A\) (từ \(L_1\) đến \(R_1\)) và một đoạn trong mảng \(B\) (từ \(L_2\) đến \(R_2\)). Với mỗi truy vấn, hãy đếm số phần tử khác nhau trong mảng được tạo thành bằng cách kết hợp các phần tử từ cả hai đoạn đã cho.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\)
• Dòng thứ hai chứa \(N\) số nguyên là các phần tử của mảng \(A\)
• Dòng thứ ba chứa \(N\) số nguyên là các phần tử của mảng \(B\)
• Dòng thứ tư chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L_1\), \(R_1\), \(L_2\), \(R_2\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra một số nguyên trên một dòng - số lượng phần tử khác nhau trong mảng kết hợp.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Q \leq 10^5\)
• \(1 \leq L_1 \leq R_1 \leq N\)
• \(1 \leq L_2 \leq R_2 \leq N\)

Ví dụ

INPUT

5
1 2 3 4 5
2 1 3 1 4
2
1 3 4 5
1 3 3 5

OUTPUT

4
4

Giải thích

• Ở truy vấn 1: mảng mới được tạo thành là: 1 2 3 1 4, có bốn phần tử khác nhau.
• Ở truy vấn 2: mảng mới được tạo thành là: 1 2 3 3 1 4, cũng có bốn phần tử khác nhau. Tuyệt vời! Đây là bài toán đếm số phần tử khác nhau trên hợp của hai đoạn, một bài khá hay và thường được giải bằng kỹ thuật tối ưu cho truy vấn đoạn ngoại tuyến.

Dưới đây là hướng dẫn giải ngắn gọn:

1. Nhận xét bài toán:

   • Chúng ta cần đếm số phần tử khác nhau trên hợp của hai đoạn A[L1..R1] và B[L2..R2].
   • Có nhiều truy vấn Q. Phương pháp duyệt từng truy vấn và dùng std::set hoặc duyệt mảng kết hợp sẽ có độ phức tạp O(Q (R1-L1+R2-L2) log(R1-L1+R2-L2)) hoặc O(Q * (R1-L1+R2-L2)), quá chậm với N, Q lên tới 10^5.
   • Đây là bài toán truy vấn trên đoạn, và chúng ta cần xử lý ngoại tuyến (offline) để đạt hiệu quả tốt hơn. Kỹ thuật Mo's Algorithm (thuật toán Mo) thường được áp dụng.

2. Áp dụng Thuật toán Mo mở rộng:

   • Thuật toán Mo cơ bản xử lý truy vấn trên một đoạn [L, R] của một mảng. Ở đây ta có truy vấn trên hai đoạn [L1, R1] và [L2, R2] từ hai mảng khác nhau. Coi như truy vấn là 4 chiều (L1, R1, L2, R2).
   • Mo's Algorithm hoạt động bằng cách sắp xếp các truy vấn theo một thứ tự đặc biệt và duy trì một "cửa sổ" hiện tại. Khi di chuyển cửa sổ từ truy vấn hiện tại sang truy vấn tiếp theo, ta chỉ cần thêm/bớt từng phần tử ở các biên, cập nhật trạng thái trong O(1) hoặc O(log N) cho mỗi lần di chuyển.
   • Với 4 biên L1, R1, L2, R2, chúng ta cần 4 con trỏ curL1, curR1, curL2, curR2 để theo dõi đoạn hiện tại.
   • Chúng ta cần một mảng đếm tần suất (hoặc hash map) để lưu số lần xuất hiện của mỗi giá trị trong hợp của hai đoạn A[curL1..curR1] và B[curL2..curR2].
   • Đồng thời, duy trì một biến distinct_count đếm số giá trị có tần suất lớn hơn 0. Khi thêm một phần tử x, nếu tần suất của x tăng từ 0 lên 1, tăng distinct_count. Khi bớt một phần tử x, nếu tần suất của x giảm từ 1 xuống 0, giảm distinct_count. Thao tác thêm/bớt và cập nhật distinct_count là O(1) (trung bình với hash map) hoặc O(1) với mảng nếu giá trị được nén.

3. Nén giá trị (Coordinate Compression):

   • Các giá trị trong mảng A và B có thể lớn, nhưng chỉ có tối đa 2*N giá trị khác nhau trong cả hai mảng. Nén các giá trị này về khoảng [0, 2N-1] để sử dụng mảng tần suất thay vì hash map, đảm bảo thao tác O(1) cho việc cập nhật tần suất.

4. Sắp xếp truy vấn (Mo's Sorting):

   • Chia khoảng [1, N] thành các khối có kích thước BlockSize. Kích thước khối tối ưu cho Mo 4 chiều là khoảng N^(1/4).
   • Sắp xếp các truy vấn (L1, R1, L2, R2) theo thứ tự:
     • Khối của L1 (chính).
     • Khối của R1.
     • Khối của L2.
     • R2.
   • Để tối ưu thêm, có thể đảo thứ tự của các thứ nguyên con (ví dụ: R2 tăng dần trong khối L2 chẵn, giảm dần trong khối L2 lẻ; khối L2 tăng dần trong khối R1 chẵn, giảm dần trong khối R1 lẻ, v.v.).

5. Thực hiện Mo's Algorithm:

   • Nén giá trị trong A và B.
   • Lưu trữ các truy vấn cùng với chỉ số ban đầu của chúng.
   • Sắp xếp các truy vấn theo tiêu chí Mo 4 chiều.
   • Khởi tạo 4 con trỏ curL1 = 0, curR1 = -1, curL2 = 0, curR2 = -1, mảng tần suất freq (kích thước 2N+1) bằng 0, và distinct_count = 0. (Lưu ý dùng chỉ số 0-based: L-1, R-1).
   • Duyệt qua các truy vấn đã sắp xếp. Đối với mỗi truy vấn (l1, r1, l2, r2):
     • Di chuyển curL1 đến l1 (thêm/bớt các phần tử A[i] khi curL1 di chuyển).
     • Di chuyển curR1 đến r1 (thêm/bớt các phần tử A[i] khi curR1 di chuyển).
     • Di chuyển curL2 đến l2 (thêm/bớt các phần tử B[i] khi curL2 di chuyển).
     • Di chuyển curR2 đến r2 (thêm/bớt các phần tử B[i] khi curR2 di chuyển).
     • Trong quá trình di chuyển, sử dụng hàm add(value) và remove(value) để cập nhật mảng freq và biến distinct_count.
     • Lưu giá trị distinct_count vào mảng kết quả cho truy vấn tương ứng (dựa vào chỉ số ban đầu của truy vấn).
   • In kết quả cho từng truy vấn theo thứ tự ban đầu.

Độ phức tạp:

• Nén giá trị: O(N log N)
• Sắp xếp truy vấn Mo 4D: O(Q log Q) hoặc O(Q) với radix sort.
• Di chuyển con trỏ trong Mo: Với block size N^(1/4), tổng số bước di chuyển của 4 con trỏ là O((N+Q) * N^(1/4)). Mỗi bước di chuyển mất O(1) sau khi nén.
• Tổng độ phức tạp thời gian: O(N log N + Q log Q + (N+Q) * N^(1/4)). Với N, Q <= 10^5, N^(1/4) \( 18, đây là độ phức tạp chấp nhận được (\)10^7-10^8).
• Độ phức tạp không gian: O(N + Q) cho mảng, truy vấn, mảng tần suất và mảng kết quả.

Làm thêm nhiều bài tập miễn phí tại đây