Khóa học CTDL và GT

Bài 30.4. Các biến thể cơ bản của Segment Tree

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Trong bài trước, chúng ta đã làm quen với Segment Tree (Cây Đoạn) và thấy được sức mạnh của nó trong việc xử lý các truy vấn trên đoạn (như tìm tổng, min, max trên một khoảng) và cập nhật điểm (thay đổi giá trị tại một vị trí cụ thể) chỉ với độ phức tạp O(log N).

Tuy nhiên, đời không như mơ, và các bài toán thực tế thường đòi hỏi nhiều hơn thế. Sẽ thế nào nếu chúng ta cần cập nhật một đoạn (ví dụ: cộng thêm 5 vào tất cả các phần tử từ chỉ số l đến r)? Nếu dùng Segment Tree cơ bản và cập nhật từng điểm trong đoạn [l, r], độ phức tạp sẽ là O(N log N) cho mỗi lần cập nhật, điều này là không chấp nhận được nếu có nhiều truy vấn cập nhật đoạn.

Đây chính là lúc chúng ta cần đến những biến thể cơ bản nhưng cực kỳ hiệu quả của Segment Tree. Chìa khóa nằm ở kỹ thuật Lazy Propagation (Lan truyền trễ), cho phép chúng ta hoãn việc áp dụng các cập nhật đoạn xuống các nút lá cho đến khi thực sự cần.

Lazy Propagation: Chìa khóa cho Range Update

Ý tưởng đằng sau Lazy Propagation rất đơn giản: khi cần cập nhật một đoạn [l, r], thay vì đi xuống tận các nút lá biểu diễn từng phần tử trong đoạn đó để cập nhật giá trị, chúng ta sẽ dừng lại ở các nút trung gian của cây mà bao phủ hoàn toàn các đoạn con nằm trong [l, r]. Tại các nút này, chúng ta không cập nhật ngay giá trị của các con, mà chỉ ghi lại "ghi chú" về việc cần phải cập nhật gì đó cho đoạn mà nút này quản lý. "Ghi chú" này được lưu trong một mảng/trường phụ thường được gọi là mảng lazy.

Khi nào thì "ghi chú" này được xử lý? Chỉ khi chúng ta đi xuống từ nút đó đến các nút con (trong quá trình truy vấn hoặc cập nhật các đoạn nhỏ hơn nằm bên dưới nút đó). Lúc này, chúng ta mới áp dụng "ghi chú" đó cho chính nút hiện tại, đẩy "ghi chú" xuống các nút con, và xóa "ghi chú" ở nút hiện tại. Quá trình "đẩy" này được gọi là propagating (lan truyền).

Kỹ thuật này đảm bảo rằng mỗi lần cập nhật hoặc truy vấn trên đoạn chỉ chạm vào O(log N) nút trên đường đi từ gốc xuống, và mỗi nút bị chạm chỉ thực hiện một lượng công việc hằng số để xử lý hoặc đẩy lazy. Do đó, cả cập nhật đoạn và truy vấn đoạn đều đạt độ phức tạp O(log N)!

Chúng ta cần thêm một mảng lazy có kích thước tương tự mảng tree (thường là 4*N nếu sử dụng 1-based indexing cho cây). lazy[node] sẽ lưu trữ thông tin về cập nhật đang chờ được áp dụng cho đoạn mà node quản lý. Ý nghĩa của lazy[node] phụ thuộc vào loại cập nhật (cộng, gán, v.v.).

Bây giờ, hãy đi sâu vào hai ví dụ phổ biến nhất: cập nhật cộng trên đoạn kết hợp với truy vấn tổng trên đoạn, và cập nhật gán trên đoạn kết hợp với truy vấn min/max trên đoạn.

Ví dụ 1: Cập nhật Cộng trên Đoạn, Truy vấn Tổng trên Đoạn

Đây là trường hợp kinh điển của Lazy Propagation. Chúng ta có một mảng ban đầu, và cần hỗ trợ hai loại thao tác:

1. Thêm một giá trị v vào tất cả các phần tử trong đoạn [l, r].
2. Tính tổng các phần tử trong đoạn [l, r].

Trong Segment Tree cơ bản, nút tree[node] lưu trữ tổng của đoạn mà nó quản lý. Với cập nhật cộng, lazy[node] sẽ lưu trữ giá trị cần được cộng thêm vào mỗi phần tử trong đoạn mà node quản lý.

Khi chúng ta đến một nút node quản lý đoạn [L, R]:

• Hàm push(node, L, R): Nếu lazy[node] khác 0 (có cập nhật chờ):
  • Áp dụng cập nhật cho nút hiện tại: tree[node] += lazy[node] * (R - L + 1) (cộng lazy[node] cho mỗi phần tử trong đoạn dài R - L + 1).
  • Nếu node không phải là nút lá (tức L != R): Đẩy cập nhật xuống các con: lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node].
  • Xóa cập nhật chờ ở nút hiện tại: lazy[node] = 0.
• Hàm update_range(node, L, R, l, r, v): Cập nhật cộng v vào đoạn [l, r] trên đoạn [L, R] của nút node.
  • Gọi push(node, L, R) trước khi xử lý nút node. Điều này đảm bảo giá trị tree[node] và lazy của con là chính xác.
  • Trường hợp 1: Đoạn [L, R] không giao với [l, r]. Bỏ qua.
  • Trường hợp 2: Đoạn [L, R] nằm hoàn toàn trong [l, r]. Áp dụng cập nhật trực tiếp: lazy[node] += v. Sau đó, gọi push(node, L, R) ngay lập tức để áp dụng lazy này lên tree[node] và đẩy xuống con (chuẩn bị cho các truy vấn/cập nhật con sau này). Hàm push này sẽ xử lý việc xóa lazy[node] về 0.
  • Trường hợp 3: Đoạn [L, R] giao một phần với [l, r]. Đẩy cập nhật xuống các con (push đã được gọi ở đầu hàm), sau đó gọi đệ quy cho con trái và con phải. Sau khi đệ quy xong, cập nhật lại tree[node] bằng tổng của tree con trái và con phải (tree[node] = tree[2*node] + tree[2*node+1]).
• Hàm query_range(node, L, R, l, r): Truy vấn tổng trên đoạn [l, r] trên đoạn [L, R] của nút node.
  • Gọi push(node, L, R) trước khi xử lý nút node.
  • Trường hợp 1: Đoạn [L, R] không giao với [l, r]. Trả về phần tử trung tính của phép tổng (0).
  • Trường hợp 2: Đoạn [L, R] nằm hoàn toàn trong [l, r]. Trả về tree[node] (vì push đã đảm bảo nó chứa tổng chính xác).
  • Trường hợp 3: Đoạn [L, R] giao một phần với [l, r]. Đẩy cập nhật xuống các con (push đã được gọi ở đầu hàm), sau đó gọi đệ quy cho con trái và con phải và trả về tổng kết quả của chúng.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MAXN = 100005; // Kích thước mảng ban đầu
long long tree[4 * MAXN]; // Mảng Segment Tree
long long lazy[4 * MAXN]; // Mảng Lazy Propagation

int N; // Kích thước thực tế của mảng
vector<int> a; // Mảng ban đầu

// Hàm xây dựng Segment Tree
// node: chỉ số nút hiện tại trong mảng tree và lazy
// L, R: đoạn mà nút node quản lý [L, R] (0-indexed)
void build(int node, int L, int R) {
    lazy[node] = 0; // Khởi tạo lazy = 0 (không có cập nhật chờ)
    if (L == R) {
        tree[node] = a[L]; // Nút lá lưu giá trị ban đầu
        return;
    }
    int mid = (L + R) / 2;
    build(2 * node, L, mid);       // Xây dựng cây con trái
    build(2 * node + 1, mid + 1, R); // Xây dựng cây con phải
    tree[node] = tree[2 * node] + tree[2 * node + 1]; // Nút cha lưu tổng của hai nút con
}

// Hàm lan truyền cập nhật lazy xuống các nút con
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
void push(int node, int L, int R) {
    if (lazy[node] != 0) { // Nếu có cập nhật chờ tại nút này
        // Áp dụng cập nhật lazy vào giá trị của nút hiện tại
        tree[node] += lazy[node] * (R - L + 1);

        if (L != R) { // Nếu không phải là nút lá
            // Đẩy cập nhật lazy xuống các nút con
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }

        lazy[node] = 0; // Xóa cập nhật chờ tại nút hiện tại
    }
}

// Hàm cập nhật cộng giá trị v vào đoạn [l, r]
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
// l, r: đoạn cần cập nhật [l, r] (0-indexed)
// v: giá trị cần cộng thêm
void update_range(int node, int L, int R, int l, int r, int v) {
    push(node, L, R); // Luôn đẩy lazy trước khi xử lý nút hiện tại

    // Trường hợp 1: Đoạn [L, R] không giao với đoạn cần cập nhật [l, r]
    if (R < l || L > r) {
        return;
    }

    // Trường hợp 2: Đoạn [L, R] nằm hoàn toàn trong đoạn cần cập nhật [l, r]
    if (l <= L && R <= r) {
        lazy[node] += v; // Thêm v vào lazy của nút này
        push(node, L, R); // Áp dụng lazy ngay lập tức và đẩy xuống con
        return;
    }

    // Trường hợp 3: Đoạn [L, R] giao một phần với đoạn cần cập nhật [l, r]
    int mid = (L + R) / 2;
    update_range(2 * node, L, mid, l, r, v);       // Đệ quy cho cây con trái
    update_range(2 * node + 1, mid + 1, R, l, r, v); // Đệ quy cho cây con phải

    // Sau khi cập nhật các con, giá trị của nút cha cần được cập nhật lại
    // Đây là điểm khác biệt quan trọng so với Segment Tree cơ bản:
    // Giá trị nút cha không đơn giản là tổng các con TRƯỚC khi push,
    // mà phải là tổng các con SAU KHI push (đã có lazy của chúng được áp dụng)
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

// Hàm truy vấn tổng trên đoạn [l, r]
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
// l, r: đoạn cần truy vấn [l, r] (0-indexed)
long long query_range(int node, int L, int R, int l, int r) {
    push(node, L, R); // Luôn đẩy lazy trước khi xử lý nút hiện tại

    // Trường hợp 1: Đoạn [L, R] không giao với đoạn cần truy vấn [l, r]
    if (R < l || L > r) {
        return 0; // Phần tử trung tính của phép tổng là 0
    }

    // Trường hợp 2: Đoạn [L, R] nằm hoàn toàn trong đoạn cần truy vấn [l, r]
    if (l <= L && R <= r) {
        return tree[node]; // Giá trị của nút hiện tại đã chính xác sau khi push
    }

    // Trường hợp 3: Đoạn [L, R] giao một phần với đoạn cần truy vấn [l, r]
    int mid = (L + R) / 2;
    long long p1 = query_range(2 * node, L, mid, l, r);       // Đệ quy cho cây con trái
    long long p2 = query_range(2 * node + 1, mid + 1, R, l, r); // Đệ quy cho cây con phải

    return p1 + p2; // Tổng kết quả của hai cây con
}

int main() {
    N = 5; // Kích thước mảng ví dụ
    a = {1, 2, 3, 4, 5}; // Mảng ban đầu

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

    cout << "Mang ban dau: ";
    for(int x : a) cout << x << " ";
    cout << endl;

    // Ví dụ truy vấn và cập nhật
    cout << "Tong doan [0, 4]: " << query_range(1, 0, N - 1, 0, 4) << endl; // Output: 15 (1+2+3+4+5)
    cout << "Tong doan [1, 3]: " << query_range(1, 0, N - 1, 1, 3) << endl; // Output: 9 (2+3+4)

    cout << "\nCap nhat cong 10 vao doan [1, 3]" << endl;
    // Mang se tro thanh {1, 12, 13, 14, 5} ve mat ly thuyet
    update_range(1, 0, N - 1, 1, 3, 10);

    cout << "Tong doan [0, 4] sau cap nhat: " << query_range(1, 0, N - 1, 0, 4) << endl; // Output: 15 + (3 * 10) = 45
    cout << "Tong doan [1, 3] sau cap nhat: " << query_range(1, 0, N - 1, 1, 3) << endl; // Output: 9 + (3 * 10) = 39
    cout << "Tong doan [2, 4] sau cap nhat: " << query_range(1, 0, N - 1, 2, 4) << endl; // Output: (13+14) + 5 = 32 (3+4+5) + (2*10) = 12 + 20 = 32

    return 0;
}

Giải thích Code (Ví dụ 1):

• Chúng ta dùng mảng tree để lưu tổng các đoạn và mảng lazy để lưu giá trị cần cộng thêm.
• build(1, 0, N-1): Xây dựng cây từ mảng a. Ban đầu, tất cả lazy đều là 0.
• push(node, L, R): Đây là hàm cốt lõi của lazy propagation cho cập nhật cộng. Nếu lazy[node] khác 0, nó nghĩa là tất cả các phần tử trong đoạn [L, R] cần được cộng thêm lazy[node]. Chúng ta áp dụng điều này vào tree[node]. Sau đó, nếu node không phải nút lá, chúng ta cộng giá trị lazy[node] vào lazy của các con, biểu thị rằng chúng cũng cần được cập nhật tương tự. Cuối cùng, đặt lazy[node] về 0 vì cập nhật đã được "lan truyền".
• update_range(node, L, R, l, r, v): Để cập nhật đoạn [l, r] với giá trị v.
  • Điều đầu tiên cần làm là gọi push(node, L, R). Điều này đảm bảo rằng bất kỳ cập nhật chờ nào tại node sẽ được áp dụng trước khi chúng ta quyết định làm gì tiếp theo với node. Điều này rất quan trọng để đảm bảo tính chính xác.
  • Nếu đoạn [L, R] hoàn toàn nằm trong [l, r], chúng ta không cần đi xuống sâu hơn. Chỉ cần thêm v vào lazy[node], và gọi push(node, L, R) ngay lập tức. Việc gọi push ở đây giúp áp dụng lazy mới này lên tree[node] và đẩy nó xuống con, chuẩn bị cho các thao tác sau này trên các đoạn con. Sau khi gọi push, lazy[node] sẽ trở về 0.
  • Nếu đoạn [L, R] chỉ giao một phần hoặc bao trùm [l, r], chúng ta đẩy lazy (push), sau đó đệ quy cho các con. Sau khi các con đã được xử lý (có thể đã nhận các cập nhật mới hoặc cũ được đẩy xuống), giá trị tree[node] cần được cập nhật lại bằng tổng của tree con trái và con phải.
• query_range(node, L, R, l, r): Để truy vấn tổng đoạn [l, r].
  • Tương tự như update_range, chúng ta phải gọi push(node, L, R) đầu tiên. Điều này đảm bảo rằng giá trị tree[node] là chính xác (đã bao gồm tất cả các cập nhật chờ) trước khi chúng ta sử dụng nó.
  • Nếu đoạn [L, R] hoàn toàn nằm trong [l, r], chúng ta trả về tree[node].
  • Nếu đoạn [L, R] chỉ giao một phần, chúng ta đẩy lazy (push) và đệ quy cho các con, rồi trả về tổng kết quả của chúng.

Lưu ý quan trọng: Việc gọi push(node, L, R) ngay đầu các hàm update_range và query_range là bắt buộc để đảm bảo tính đúng đắn. Nó giải quyết mọi cập nhật chờ tại nút hiện tại trước khi chúng ta xử lý nút đó hoặc đi xuống các con.

Ví dụ 2: Cập nhật Gán trên Đoạn, Truy vấn Min/Max trên Đoạn

Loại biến thể này phức tạp hơn một chút ở chỗ cách chúng ta xử lý lazy. Thay vì cộng thêm, chúng ta gán một giá trị mới cho tất cả các phần tử trong đoạn.

• Cập nhật Gán: Khi cập nhật một đoạn [l, r] với giá trị v, tất cả các phần tử trong đoạn đó sẽ có giá trị là v, bất kể giá trị ban đầu của chúng là gì.
• Truy vấn Min/Max: Tìm giá trị nhỏ nhất hoặc lớn nhất trong đoạn [l, r].

Với cập nhật gán, lazy[node] sẽ lưu trữ giá trị mới cần được gán cho tất cả các phần tử trong đoạn mà node quản lý. Chúng ta cần một cách để biểu thị rằng không có cập nhật gán chờ (ví dụ: sử dụng một giá trị sentinel như LLONG_MAX hoặc INT_MIN tùy thuộc vào loại giá trị và phép toán, hoặc dùng một mảng boolean đi kèm).

Trong ví dụ này, chúng ta sẽ dùng LLONG_MAX để biểu thị không có cập nhật gán chờ, giả sử các giá trị trong mảng không bao giờ đạt đến LLONG_MAX.

Khi chúng ta đến một nút node quản lý đoạn [L, R]:

• Hàm push(node, L, R): Nếu lazy[node] khác LLONG_MAX (có cập nhật gán chờ):
  • Áp dụng cập nhật gán cho nút hiện tại: tree[node] = lazy[node]. (Vì tất cả phần tử trong đoạn đều có giá trị lazy[node], min/max/tổng đều là lazy[node] nhân chiều dài đoạn - ở đây ta chỉ cần min/max nên lưu giá trị đó là đủ).
  • Nếu node không phải là nút lá: Đẩy cập nhật gán xuống các con: lazy[2*node] = lazy[node], lazy[2*node+1] = lazy[node]. (Cập nhật gán mới sẽ ghi đè lên mọi cập nhật gán hoặc cộng/trừ cũ đang chờ ở con).
  • Xóa cập nhật chờ ở nút hiện tại: lazy[node] = LLONG_MAX.
• Hàm update_range(node, L, R, l, r, v): Cập nhật gán giá trị v vào đoạn [l, r] trên đoạn [L, R] của nút node.
  • Gọi push(node, L, R) trước khi xử lý nút node.
  • Trường hợp 1: Không giao. Bỏ qua.
  • Trường hợp 2: Nằm hoàn toàn trong [l, r]. Áp dụng cập nhật gán: lazy[node] = v. Sau đó, gọi push(node, L, R) ngay lập tức.
  • Trường hợp 3: Giao một phần. Đẩy cập nhật xuống các con (push), sau đó gọi đệ quy cho con trái và con phải. Sau khi đệ quy, cập nhật lại tree[node] bằng kết quả kết hợp của tree con trái và con phải (ví dụ: min(tree[2*node], tree[2*node+1]) cho truy vấn min).
• Hàm query_range(node, L, R, l, r): Truy vấn min/max trên đoạn [l, r] trên đoạn [L, R] của nút node.
  • Gọi push(node, L, R) trước khi xử lý nút node.
  • Trường hợp 1: Không giao. Trả về phần tử trung tính cho min/max (ví dụ: LLONG_MAX cho min, LLONG_MIN cho max).
  • Trường hợp 2: Nằm hoàn toàn trong [l, r]. Trả về tree[node].
  • Trường hợp 3: Giao một phần. Đẩy lazy (push), sau đó gọi đệ quy và kết hợp kết quả (min hoặc max).

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits> // For LLONG_MAX, LLONG_MIN

using namespace std;

const int MAXN = 100005; // Kích thước mảng ban đầu
long long tree_min[4 * MAXN]; // Segment Tree cho Min
long long lazy_set[4 * MAXN]; // Mảng Lazy Propagation cho phép Gán

const long long NO_LAZY_SET = LLONG_MAX; // Giá trị sentinel cho biết không có cập nhật gán chờ

int N; // Kích thước thực tế của mảng
vector<int> a; // Mảng ban đầu

// Hàm xây dựng Segment Tree cho Min
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
void build_min(int node, int L, int R) {
    lazy_set[node] = NO_LAZY_SET; // Khởi tạo lazy = sentinel
    if (L == R) {
        tree_min[node] = a[L]; // Nút lá lưu giá trị ban đầu
        return;
    }
    int mid = (L + R) / 2;
    build_min(2 * node, L, mid);       // Xây dựng cây con trái
    build_min(2 * node + 1, mid + 1, R); // Xây dựng cây con phải
    tree_min[node] = min(tree_min[2 * node], tree_min[2 * node + 1]); // Nút cha lưu min của hai nút con
}

// Hàm lan truyền cập nhật gán lazy xuống các nút con
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
void push_set(int node, int L, int R) {
    if (lazy_set[node] != NO_LAZY_SET) { // Nếu có cập nhật gán chờ tại nút này
        // Áp dụng cập nhật gán vào giá trị của nút hiện tại
        // Đối với min/max, khi gán 1 giá trị cho toàn bộ đoạn, min/max của đoạn chính là giá trị đó
        tree_min[node] = lazy_set[node];

        if (L != R) { // Nếu không phải là nút lá
            // Đẩy cập nhật gán lazy xuống các nút con (ghi đè lazy cũ của con)
            lazy_set[2 * node] = lazy_set[node];
            lazy_set[2 * node + 1] = lazy_set[node];
        }

        lazy_set[node] = NO_LAZY_SET; // Xóa cập nhật chờ tại nút hiện tại
    }
}

// Hàm cập nhật gán giá trị v vào đoạn [l, r]
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
// l, r: đoạn cần cập nhật [l, r]
// v: giá trị cần gán
void update_range_set(int node, int L, int R, int l, int r, int v) {
    push_set(node, L, R); // Luôn đẩy lazy trước khi xử lý nút hiện tại

    // Trường hợp 1: Không giao
    if (R < l || L > r) {
        return;
    }

    // Trường hợp 2: Nằm hoàn toàn trong đoạn cần cập nhật [l, r]
    if (l <= L && R <= r) {
        lazy_set[node] = v; // Gán v vào lazy của nút này
        push_set(node, L, R); // Áp dụng lazy ngay lập tức và đẩy xuống con
        return;
    }

    // Trường hợp 3: Giao một phần
    int mid = (L + R) / 2;
    update_range_set(2 * node, L, mid, l, r, v);       // Đệ quy cho cây con trái
    update_range_set(2 * node + 1, mid + 1, R, l, r, v); // Đệ quy cho cây con phải

    // Sau khi cập nhật các con, giá trị min của nút cha cần được cập nhật lại
    tree_min[node] = min(tree_min[2 * node], tree_min[2 * node + 1]);
}

// Hàm truy vấn min trên đoạn [l, r]
// node: chỉ số nút hiện tại
// L, R: đoạn mà nút node quản lý [L, R]
// l, r: đoạn cần truy vấn [l, r]
long long query_range_min(int node, int L, int R, int l, int r) {
    push_set(node, L, R); // Luôn đẩy lazy trước khi xử lý nút hiện tại

    // Trường hợp 1: Không giao
    if (R < l || L > r) {
        return LLONG_MAX; // Phần tử trung tính cho phép min là giá trị rất lớn
    }

    // Trường hợp 2: Nằm hoàn toàn trong đoạn cần truy vấn [l, r]
    if (l <= L && R <= r) {
        return tree_min[node]; // Giá trị của nút hiện tại đã chính xác sau khi push
    }

    // Trường hợp 3: Giao một phần
    int mid = (L + R) / 2;
    long long p1 = query_range_min(2 * node, L, mid, l, r);       // Đệ quy cho cây con trái
    long long p2 = query_range_min(2 * node + 1, mid + 1, R, l, r); // Đệ quy cho cây con phải

    return min(p1, p2); // Min kết quả của hai cây con
}

int main() {
    N = 5; // Kích thước mảng ví dụ
    a = {10, 2, 15, 4, 8}; // Mảng ban đầu

    // Xây dựng Segment Tree cho Min
    build_min(1, 0, N - 1);

    cout << "Mang ban dau: ";
    for(int x : a) cout << x << " ";
    cout << endl;

    // Ví dụ truy vấn và cập nhật
    cout << "Min doan [0, 4]: " << query_range_min(1, 0, N - 1, 0, 4) << endl; // Output: 2
    cout << "Min doan [1, 3]: " << query_range_min(1, 0, N - 1, 1, 3) << endl; // Output: 2

    cout << "\nCap nhat gan 5 vao doan [0, 2]" << endl;
    // Mang se tro thanh {5, 5, 5, 4, 8} ve mat ly thuyet
    update_range_set(1, 0, N - 1, 0, 2, 5);

    cout << "Min doan [0, 4] sau cap nhat: " << query_range_min(1, 0, N - 1, 0, 4) << endl; // Output: 4
    cout << "Min doan [0, 2] sau cap nhat: " << query_range_min(1, 0, N - 1, 0, 2) << endl; // Output: 5
    cout << "Min doan [2, 4] sau cap nhat: " << query_range_min(1, 0, N - 1, 2, 4) << endl; // Output: min(5, 4, 8) = 4

    cout << "\nCap nhat gan 20 vao doan [3, 4]" << endl;
     // Mang se tro thanh {5, 5, 5, 20, 20} ve mat ly thuyet
    update_range_set(1, 0, N - 1, 3, 4, 20);

    cout << "Min doan [0, 4] sau cap nhat: " << query_range_min(1, 0, N - 1, 0, 4) << endl; // Output: 5
    cout << "Min doan [2, 3] sau cap nhat: " << query_range_min(1, 0, N - 1, 2, 3) << endl; // Output: min(5, 20) = 5

    return 0;
}

Giải thích Code (Ví dụ 2):

• Chúng ta dùng mảng tree_min để lưu giá trị min trên các đoạn và mảng lazy_set để lưu giá trị cần gán. NO_LAZY_SET là giá trị đặc biệt biểu thị không có cập nhật gán.
• build_min: Xây dựng cây tương tự Segment Tree cơ bản, nhưng kết hợp các giá trị bằng phép min.
• push_set(node, L, R): Nếu lazy_set[node] không phải NO_LAZY_SET, nghĩa là tất cả phần tử trong đoạn [L, R] cần được gán giá trị lazy_set[node]. Đối với truy vấn min/max (hoặc thậm chí sum khi gán), khi tất cả phần tử đều có giá trị v, thì min, max, tổng của đoạn đó đều có thể suy ra từ v và chiều dài đoạn. Ở đây, vì ta chỉ cần min/max của đoạn con khi đi xuống, ta chỉ cần cập nhật tree_min[node] = lazy_set[node]. Quan trọng: Khi đẩy cập nhật gán xuống con, chúng ta ghi đè bất kỳ giá trị lazy nào đang chờ ở con (lazy_set[2*node] = lazy_set[node]). Điều này khác với cập nhật cộng, nơi lazy được cộng dồn. Cuối cùng, đặt lazy_set[node] về NO_LAZY_SET.
• update_range_set: Cập nhật gán giá trị v vào đoạn [l, r]. Logic tương tự như cập nhật cộng, nhưng khi đoạn [L, R] nằm hoàn toàn trong [l, r], chúng ta đặt lazy_set[node] = v và gọi push_set. Khi đệ quy và kết hợp kết quả, sử dụng phép min.
• query_range_min: Truy vấn min trên đoạn [l, r]. Logic tương tự, luôn gọi push_set trước, và sử dụng phép min khi kết hợp kết quả đệ quy. Phần tử trung tính cho min là giá trị rất lớn (LLONG_MAX).

Lưu ý quan trọng: Cách xử lý lazy trong hàm push phụ thuộc hoàn toàn vào loại cập nhật và loại truy vấn.

• Cập nhật cộng: Lazy được cộng dồn khi đẩy xuống con. Giá trị nút cha được cập nhật bằng tổng giá trị ban đầu + lazy * chiều dài đoạn.
• Cập nhật gán: Lazy được ghi đè khi đẩy xuống con. Giá trị nút cha được cập nhật bằng giá trị lazy.
• Nếu có nhiều loại cập nhật (ví dụ: vừa cộng, vừa gán), lazy cần lưu nhiều thông tin hơn (ví dụ: 2 trường lazy: 1 cho gán, 1 cho cộng), và hàm push sẽ phức tạp hơn để xử lý thứ tự áp dụng các cập nhật này (thường gán được áp dụng trước, sau đó đến cộng/trừ).

Phân tích độ phức tạp

Với Lazy Propagation, cả thao tác update_range và query_range đều có độ phức tạp là O(log N).

• Giải thích: Mỗi khi thực hiện cập nhật hoặc truy vấn, chúng ta đi xuống cây. Trên mỗi cấp độ của cây, chúng ta chỉ xử lý tối đa một số nút nhất định (thường là 2-4 nút) tại ranh giới của đoạn truy vấn/cập nhật, và một số nút khác nằm hoàn toàn trong đoạn. Đối với các nút nằm hoàn toàn trong đoạn, chúng ta hoặc áp dụng lazy và dừng lại (update), hoặc sử dụng giá trị đã được đẩy lazy và dừng lại (query). Đối với các nút ở ranh giới, chúng ta đẩy lazy và tiếp tục đệ quy. Vì chiều cao của cây là O(log N) và công việc tại mỗi nút (đẩy lazy, kết hợp kết quả) là O(1) (hoặc O của phép toán kết hợp), tổng độ phức tạp cho mỗi thao tác là O(log N).
• Hàm build vẫn mất O(N) thời gian.
• Không gian bộ nhớ cần thiết là O(N) cho mảng tree và O(N) cho mảng lazy.

Bài tập ví dụ:

Bob và truy vấn mảng

Trong một buổi đánh giá dự án bất động sản, FullHouse Dev được đối tác đưa ra một bài toán thú vị về xử lý dữ liệu. Họ cần phải xây dựng một hệ thống quản lý thông tin với các thao tác phức tạp trên một mảng số.

Bài toán

FullHouse Dev có một mảng \(A\) gồm \(N\) số nguyên. Ban đầu, tất cả các phần tử trong mảng đều bằng 0. Họ cần thực hiện \(Q\) thao tác trên mảng này.

Có ba loại thao tác có thể thực hiện:

1. Thao tác 1 \(X\): Cập nhật giá trị của \(A[X]\) thành \(2 * A[X] + 1\)
2. Thao tác 2 \(X\): Cập nhật giá trị của \(A[X]\) thành \(⌊A[X]/2⌋\), trong đó \(⌊x⌋\) là hàm làm tròn xuống
3. Thao tác 3 \(X\) \(Y\): Lấy tất cả các \(A[i]\) với \(X ≤ i ≤ Y\) và chuyển đổi chúng thành chuỗi nhị phân tương ứng. Sau đó nối tất cả các chuỗi nhị phân này và đếm tổng số ký tự '1' trong chuỗi kết quả.

Lưu ý: Đảm bảo có ít nhất 1 truy vấn loại 3 trong mỗi bộ test. Tất cả các phần tử mảng sẽ nằm trong giới hạn số nguyên 64 bit.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) cách nhau bởi dấu cách
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một trong ba loại thao tác như đã mô tả ở trên

OUTPUT FORMAT:

• Với mỗi truy vấn loại 3, in ra số lượng ký tự '1' trong chuỗi kết quả

Ràng buộc:

• \(1 ≤ N ≤ 10^5\)
• \(1 ≤ Q ≤ 10^5\)
• \(1 ≤ X, Y ≤ N\)

Ví dụ

INPUT

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

OUTPUT

3
2

Giải thích

Ban đầu, \(A=[0,0,0,0,0]\)

Sau truy vấn 1: \(A=[1,0,0,0,0]\)

Sau truy vấn 2: \(A=[1,1,0,0,0]\)

Sau truy vấn 3: \(A=[1,1,1,0,0]\)

Với truy vấn 4, số lượng số '1' trong biểu diễn nhị phân của \(A[1]=A[2]=A[3]=1\). Vì vậy, kết quả là 3.

Với truy vấn 5, kết quả là 2. Tuyệt vời, đây là hướng dẫn giải bài toán "Bob và truy vấn mảng" bằng C++ sử dụng cấu trúc dữ liệu phù hợp mà không cung cấp code hoàn chỉnh:

1. Nhận dạng bài toán: Bài toán yêu cầu thực hiện các thao tác cập nhật điểm (Type 1 & 2) và truy vấn tổng trên một đoạn (Type 3). Đặc biệt, truy vấn loại 3 yêu cầu tính tổng số bit '1' trong biểu diễn nhị phân của các phần tử trong một đoạn. Ràng buộc N và Q lên đến 10^5 cho thấy một giải pháp O(NQ) hoặc O(QN*log(max_value)) là quá chậm. Cần một cấu trúc dữ liệu hỗ trợ cập nhật điểm và truy vấn đoạn hiệu quả hơn.

2. Lựa chọn cấu trúc dữ liệu: Bài toán này rất phù hợp với Segment Tree (Cây phân đoạn). Segment Tree cho phép cập nhật một phần tử trong mảng ban đầu trong O(log N) và truy vấn tổng (hoặc các phép kết hợp khác) trên một đoạn trong O(log N).

3. Segment Tree Lưu trữ gì?

   • Truy vấn loại 3 yêu cầu tổng số bit '1' trong biểu diễn nhị phân của các số trong đoạn. Do đó, mỗi nút trên Segment Tree nên lưu trữ tổng số bit '1' của các phần tử trong đoạn mà nút đó quản lý.
   • Để thực hiện cập nhật loại 1 và 2, chúng ta cần biết giá trị hiện tại của phần tử A[X] để tính giá trị mới (2*A[X]+1 hoặc A[X]/2). Segment Tree chỉ lưu tổng số bit '1', không lưu giá trị. Có hai cách để giải quyết:
     • Cách 1: Duy trì mảng A ban đầu song song với Segment Tree. Khi cập nhật, thay đổi giá trị trong mảng A, tính lại số bit '1' của phần tử đó, sau đó cập nhật giá trị (số bit '1') tại nút lá tương ứng trong Segment Tree và lan truyền lên trên.
     • Cách 2: Lưu trữ giá trị A[i] trực tiếp tại nút lá tương ứng trong Segment Tree. Các nút internal chỉ lưu tổng số bit '1'. Cách này có thể gọn hơn.

4. Chi tiết triển khai Segment Tree:

   • Cấu trúc nút: Nếu chọn Cách 2, nút lá có thể lưu long long value và int popcount. Nút internal chỉ cần lưu long long total_popcount (tổng số bit '1' của các con).
   • Khởi tạo (Build): Ban đầu mảng A toàn 0. Xây dựng cây, các nút lá sẽ có value = 0, popcount = 0. Các nút internal có total_popcount = 0. Thời gian O(N).
   • Cập nhật (Update) Loại 1 & 2:
     • Tìm đến nút lá tương ứng với chỉ số X (nhớ điều chỉnh chỉ số từ 1-based sang 0-based nếu cần).
     • Lấy giá trị v = A[X] (hoặc v = node.value nếu lưu ở nút lá).
     • Nếu là Loại 1: new_v = 2 * v + 1.
     • Nếu là Loại 2: new_v = v / 2.
     • Cập nhật giá trị: A[X] = new_v (hoặc node.value = new_v).
     • Tính lại số bit '1' cho giá trị mới: new_popcount = __builtin_popcountll(new_v) (sử dụng hàm built-in của GCC/Clang cho long long để đếm bit '1' hiệu quả).
     • Cập nhật số bit '1' tại nút lá: node.popcount = new_popcount.
     • Lan truyền sự thay đổi lên các nút cha bằng cách cập nhật lại total_popcount của chúng (nút cha = tổng total_popcount của các con) cho đến gốc. Thời gian O(log N).
   • Truy vấn (Query) Loại 3:
     • Thực hiện truy vấn tổng đoạn trên Segment Tree cho đoạn [X, Y] (điều chỉnh chỉ số).
     • Hàm truy vấn sẽ duyệt cây và trả về tổng total_popcount của các nút con phủ toàn bộ đoạn truy vấn. Thời gian O(log N).

5. Sử dụng kiểu dữ liệu 64-bit: Giá trị của các phần tử mảng có thể tăng rất lớn do thao tác 2*A[X]+1. Đảm bảo sử dụng long long trong C++ để lưu trữ giá trị của các phần tử mảng và tổng số bit '1' nếu cần (dù tổng số bit '1' trong một đoạn N phần tử, mỗi phần tử tối đa 64 bit là N*64, vẫn có thể vượt quá int, nên lưu tổng bằng long long cho an toàn). Hàm __builtin_popcountll là cần thiết để đếm bit '1' cho long long.

6. Ràng buộc và Tối ưu: Với N, Q = 10^5, giải pháp Segment Tree (O(Q log N)) là đủ nhanh. Không cần tối ưu phức tạp hơn.

Tóm tắt hướng giải:

1. Sử dụng Segment Tree.
2. Mỗi nút trên cây lưu trữ tổng số bit '1' của các phần tử trong đoạn mà nó quản lý.
3. Để thực hiện cập nhật (Type 1 & 2), cần lưu trữ giá trị thực của các phần tử mảng (dùng long long), có thể lưu ở các nút lá của Segment Tree hoặc trong một mảng riêng.
4. Khi cập nhật A[X]: tính giá trị mới, đếm số bit '1' của giá trị mới bằng __builtin_popcountll, và cập nhật Segment Tree từ nút lá tương ứng lên gốc.
5. Khi truy vấn đoạn [X, Y] (Type 3): thực hiện truy vấn tổng trên Segment Tree cho đoạn này.
6. Chú ý xử lý chỉ số 1-based của đề bài và 0-based của mảng/Segment Tree trong C++.

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