Trong các cấu trúc dữ liệu phân đoạn như Segment Tree (Cây phân đoạn) hay các loại cây cân bằng, hàm pushdown đóng vai trò then chốt trong việc tối ưu hóa hiệu suất. Kỹ thuật này thường được gọi là Lazy Propagation (Lan truyền lười), cho phép chúng ta trì hoãn việc cập nhật các nút con cho đến khi thực sự cần thiết, từ đó giảm độ phức tạp từ $O(N)$ xuống $O(\log N)$ cho các thao tác trên đoạn.

Nguyên lý cốt lõi của pushdown là khi một khoảng được cập nhật hoàn toàn, chúng ta chỉ ghi nhận thay đổi tại nút đại diện cho khoảng đó thông qua một "biến lười" (lazy tag) mà không đi sâu xuống các nút con. Chỉ khi một thao tác truy vấn hoặc cập nhật khác yêu cầu truy cập vào các nút con, giá trị từ biến lười mới được đẩy xuống.

Dưới đây là một ví dụ về hàm cập nhật khoảng cộng thêm một giá trị $v$:

void updateRange(int node, int start, int end, long long v) {
    if (tree[node].left >= start && tree[node].right <= end) {
        tree[node].sum += v * (tree[node].right - tree[node].left + 1);
        tree[node].lazyAdd += v;
        return;
    }
    
    // Đẩy giá trị lười xuống các con trước khi đi sâu hơn
    pushDown(node);
    
    int mid = (tree[node].left + tree[node].right) >> 1;
    if (start <= mid) updateRange(node * 2, start, end, v);
    if (end > mid) updateRange(node * 2 + 1, start, end, v);
    
    // Cập nhật lại giá trị nút cha dựa trên các con
    pushUp(node);
}

Trong đoạn mã trên, tree[node].sum lưu trữ tổng của đoạn và tree[node].lazyAdd lưu trữ giá trị chờ để truyền cho các con. Khi một truy vấn tìm kiếm nằm trọn trong phạm vi của nút, chúng ta cập nhật ngay lập tức và dừng lại. Để đảm bảo tính chính xác cho các truy vấn sau này, hàm query cũng cần gọi pushdown:

long long querySum(int node, int start, int end) {
    if (tree[node].left >= start && tree[node].right <= end) {
        return tree[node].sum;
    }
    
    pushDown(node);
    
    int mid = (tree[node].left + tree[node].right) >> 1;
    long long total = 0;
    if (start <= mid) total += querySum(node * 2, start, end);
    if (end > mid) total += querySum(node * 2 + 1, start, end);
    
    return total;
}

Nếu không thực hiện pushdown trong quá trình cập nhật, một lỗi nghiêm trọng sẽ xảy ra: các thay đổi cũ bị lưu lại ở nút cha có thể ghi đè hoặc làm sai lệch kết quả khi nút cha được tính toán lại từ các nút con chưa được cập nhật. Ví dụ, nếu bạn cập nhật đoạn $[1, 10]$ rồi sau đó cập nhật đoạn $[5, 5]$, nếu không đẩy giá trị từ nút đại diện $[1, 10]$ xuống, nút $[5, 5]$ sẽ mang giá trị cũ, và khi thực hiện pushup, tổng của đoạn $[1, 10]$ sẽ bị sai.

Xử lý đa tác vụ: Cộng và Nhân trên đoạn

Khi cấu trúc dữ liệu yêu cầu xử lý đồng thời nhiều loại phép toán (như vừa cộng vừa nhân), hàm pushdown trở nên phức tạp hơn. Quy tắc thông thường là ưu tiên phép nhân trước phép cộng để duy trì tính nhất quán của biểu thức $val = (original \times multiplier) + adder$.

void pushDown(int p) {
    long long m = tree[p].mulTag;
    long long a = tree[p].addTag;
    
    if (m == 1 && a == 0) return;

    int left = p * 2, right = p * 2 + 1;

    // Cập nhật nút con bên trái
    tree[left].sum = (tree[left].sum * m + a * (tree[left].right - tree[left].left + 1)) % MOD;
    tree[left].mulTag = (tree[left].mulTag * m) % MOD;
    tree[left].addTag = (tree[left].addTag * m + a) % MOD;

    // Cập nhật nút con bên phải
    tree[right].sum = (tree[right].sum * m + a * (tree[right].right - tree[right].left + 1)) % MOD;
    tree[right].mulTag = (tree[right].mulTag * m) % MOD;
    tree[right].addTag = (tree[right].addTag * m + a) % MOD;

    // Reset tag của nút hiện tại
    tree[p].mulTag = 1;
    tree[p].addTag = 0;
}

Sở dĩ chúng ta phải cập nhật addTag bằng cách nhân nó với mulTag hiện tại là vì khi một đoạn đang có một giá trị cộng chờ sẵn ($a$), nếu ta nhân toàn bộ đoạn đó với $m$, thì giá trị cộng đó cũng phải được nhân lên tương ứng. Điều này đảm bảo tính phân phối của phép nhân đối với phép cộng trong toán học.

Hàm pushdown không chỉ giới hạn trong Segment Tree mà còn là kỹ thuật nền tảng cho các thao tác đảo ngược đoạn trong Splay Tree hay Treap. Việc hiểu rõ cơ chế lan truyền này là chìa khóa để giải quyết các bài toán xử lý khoảng hiệu quả.