Lazy propagation: cộng cả đoạn, hỏi tổng bằng Segment Tree

Vì sao cập nhật từng điểm chưa đủ?

Segment Tree cơ bản gán một điểm rồi sửa các tổ tiên trong O(log n). Nếu muốn cộng x cho cả đoạn dài k và gọi cập nhật điểm k lần, chi phí thành O(k log n). Khi nhiều cập nhật phủ gần toàn mảng, lợi ích truy vấn nhanh không cứu được phần cập nhật quá tốn kém.

Với tổng đoạn, cộng cùng x cho mọi phần tử có một ảnh hưởng gọn: tổng tăng x nhân số phần tử. Ta có thể cập nhật ngay thông tin của một nút được phủ kín mà chưa cần xuống từng lá. Nhãn lười ghi rằng con của nó còn nợ thay đổi này để xử lý khi cần.

Không nên hiểu “lười” là kết quả cha cũng sai và sẽ sửa sau. Bất biến quan trọng là thống kê ở một nút đã bao gồm nhãn của chính nó; chỉ các nút phía dưới chưa nhận hết. Hiểu nhầm này dễ dẫn tới cộng nhãn hai lần khi truy vấn.

apply: sửa tổng và ghi nợ cho con

Với nút đại diện [l,r), độ dài là r−l. Cộng value cho cả đoạn làm tree[p] tăng value·(r−l), đồng thời tag[p] tăng value. Nếu nút đã có nhãn +3 rồi nhận +2, hai lần cộng hợp thành +5.

Ví dụ gốc [0,5) ban đầu có tổng 15. Nhận +2 cho toàn đoạn thì tổng thành 25, tag thành 2. Không sửa 15 thành 17 vì có năm phần tử đều được cộng. Nếu có truy vấn hỏi đúng toàn đoạn lúc này, trả 25 ngay mà không cần đi xuống.

Trên bài min đoạn với cập nhật cộng đều, min chỉ tăng value chứ không nhân độ dài. Vì vậy apply phải khớp loại thống kê đang lưu. Cùng một nhãn cộng nhưng tác động lên tổng và lên min khác nhau; không sao chép công thức x·len sang mọi Node.

push: truyền đúng một lần trước khi đi sâu

Khi cần xử lý một phần của nút đang có nhãn, gọi apply cho hai con với tag của cha. Mỗi con tự nhân với độ dài của nó khi sửa tổng. Sau đó đặt tag cha về 0 vì món nợ này đã được chuyển xuống.

Trong hình, con trái [0,2) có tổng 3 được cộng 2·2 thành 7. Con phải [2,5) có tổng 12 được cộng 2·3 thành 18. Gốc vẫn tổng 25, tag về 0; hai con có tag +2 vì chúng lại còn nợ các cháu tương ứng. Không cộng thêm 10 vào gốc lần nữa trong push.

Với lá, không có con nên không cần truyền tiếp. Với tag=0 trong mô hình cộng, không có thay đổi chờ nên push có thể bỏ qua. Nếu đổi sang mô hình gán, giá trị 0 lại có thể là một lệnh gán thật; khi đó cần cờ có nhãn riêng, không được dùng 0 làm dấu luôn luôn “không có gì”.

Ba trường hợp giao với đoạn cập nhật

Nếu đoạn nút không giao truy vấn, bỏ qua. Nếu bị phủ toàn bộ, apply ngay rồi dừng nhánh. Nếu chỉ giao một phần, push trước, đệ quy vào hai con, sau đó pull bằng tổng hai con. Mỗi bước có vai trò riêng: push bảo đảm đọc con đúng, pull bảo đảm cha khớp các con sau thay đổi cục bộ.

Đừng xuống con rồi mới push nhãn cha. Lúc đó thao tác mới đang dựa trên thống kê con cũ, và thứ tự hợp các cập nhật có thể bị sai. Với phép cộng đơn giản một số lỗi còn tình cờ bị che, nhưng khi thêm gán hoặc nhân thì thứ tự rất quan trọng.

Truy vấn tổng cũng có ba trường hợp tương tự: không giao trả 0, phủ kín trả tree[p], giao một phần thì push rồi cộng kết quả hai nhánh. Truy vấn có thể làm cách nhãn được phân bố trong cây thay đổi, nhưng không đổi mảng logic và các đáp án tiếp theo.

Chạy tay ví dụ có cập nhật một phần

Tệp mặc định bắt đầu [1,2,3,4,5], hỏi tổng toàn mảng được 15. Cộng 2 cho [1,4), chỉ các vị trí 1,2,3 thay đổi; mảng logic thành [1,4,5,6,5]. Tổng toàn mảng là 21, tổng [2,4) là 5+6=11.

Hình ở đầu dùng một cập nhật toàn mảng riêng để nhìn rõ tag tại gốc; bảng này là luồng mặc định thật của chương trình. Cả hai đều minh họa cùng bất biến, không cần cây luôn có tag ở gốc mới gọi là lazy propagation.

Code C++ và Python

#include <iostream>
#include <vector>
using namespace std;
class LazySum{
    int n;vector<long long> tree,tag;
    void build(int p,int l,int r,const vector<long long>& a){
        if(r-l==1){tree[p]=a[l];return;}
        int mid=(l+r)/2;build(2*p,l,mid,a);build(2*p+1,mid,r,a);tree[p]=tree[2*p]+tree[2*p+1];
    }
    void apply(int p,int l,int r,long long value){tree[p]+=value*(r-l);tag[p]+=value;}
    void push(int p,int l,int r){
        if(tag[p]==0 || r-l==1)return;
        int mid=(l+r)/2;apply(2*p,l,mid,tag[p]);apply(2*p+1,mid,r,tag[p]);tag[p]=0;
    }
    void add_impl(int p,int l,int r,int ql,int qr,long long value){
        if(qr<=l || r<=ql)return;
        if(ql<=l && r<=qr){apply(p,l,r,value);return;}
        push(p,l,r);int mid=(l+r)/2;
        add_impl(2*p,l,mid,ql,qr,value);add_impl(2*p+1,mid,r,ql,qr,value);
        tree[p]=tree[2*p]+tree[2*p+1];
    }
    long long sum_impl(int p,int l,int r,int ql,int qr){
        if(qr<=l || r<=ql)return 0;
        if(ql<=l && r<=qr)return tree[p];
        push(p,l,r);int mid=(l+r)/2;
        return sum_impl(2*p,l,mid,ql,qr)+sum_impl(2*p+1,mid,r,ql,qr);
    }
public:
    explicit LazySum(const vector<long long>& a):n(a.size()),tree(4*n,0),tag(4*n,0){build(1,0,n,a);}
    void add(int l,int r,long long value){if(l<r)add_impl(1,0,n,l,r,value);}
    long long sum(int l,int r){return l<r ? sum_impl(1,0,n,l,r):0;}
};
int main(){
    int n,q;
    if(cin>>n>>q){
        vector<long long>a(n);for(auto& x:a)cin>>x;LazySum t(a);
        for(int z=0;z<q;++z){char op;int l,r;cin>>op>>l>>r;
            if(op=='A'){long long value;cin>>value;t.add(l,r,value);}else cout<<t.sum(l,r)<<'\n';}
    }else{LazySum t({1,2,3,4,5});cout<<t.sum(0,5)<<'\n';t.add(1,4,2);cout<<t.sum(0,5)<<'\n'<<t.sum(2,4)<<'\n';}
}

import sys

class LazySum:
    def __init__(self,a):
        self.n=len(a);self.tree=[0]*(4*self.n);self.tag=[0]*(4*self.n)
        def build(p,l,r):
            if r-l==1:
                self.tree[p]=a[l];return
            mid=(l+r)//2;build(2*p,l,mid);build(2*p+1,mid,r)
            self.tree[p]=self.tree[2*p]+self.tree[2*p+1]
        build(1,0,self.n)

    def _apply(self,p,l,r,value):
        self.tree[p]+=value*(r-l);self.tag[p]+=value

    def _push(self,p,l,r):
        if not self.tag[p] or r-l==1:
            return
        mid=(l+r)//2
        self._apply(2*p,l,mid,self.tag[p]);self._apply(2*p+1,mid,r,self.tag[p]);self.tag[p]=0

    def add(self,left,right,value):
        def run(p,l,r):
            if right<=l or r<=left:
                return
            if left<=l and r<=right:
                self._apply(p,l,r,value);return
            self._push(p,l,r);mid=(l+r)//2;run(2*p,l,mid);run(2*p+1,mid,r)
            self.tree[p]=self.tree[2*p]+self.tree[2*p+1]
        if left<right:
            run(1,0,self.n)

    def sum(self,left,right):
        def run(p,l,r):
            if right<=l or r<=left:
                return 0
            if left<=l and r<=right:
                return self.tree[p]
            self._push(p,l,r);mid=(l+r)//2
            return run(2*p,l,mid)+run(2*p+1,mid,r)
        return run(1,0,self.n) if left<right else 0

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    if lines:
        n,q=map(int,lines[0].split());t=LazySum(list(map(int,lines[1].split())))
        for line in lines[2:2+q]:
            op,*args=line.split();args=list(map(int,args))
            if op=='A':
                t.add(*args)
            else:
                print(t.sum(*args))
    else:
        t=LazySum([1,2,3,4,5]);print(t.sum(0,5));t.add(1,4,2);print(t.sum(0,5));print(t.sum(2,4))

Chạy không input in ba dòng 15,21,11. Input riêng có n,q, một dòng n giá trị và q lệnh. A l r value cộng value cho [l,r); Q l r hỏi tổng [l,r). n dương, các biên hợp lệ và có thể l=r. Cập nhật rỗng không làm gì, tổng đoạn rỗng bằng 0.

C++ dùng long long cho tree và tag. Mọi tổng, nhãn cộng dồn và tích value với độ dài cần vừa miền kiểu này; chỉ kiểm một giá trị input chưa đủ vì nhiều cập nhật có thể tích lại. Python có số nguyên lớn nhưng vẫn cần tính bộ nhớ và số thao tác theo giới hạn thực tế.

Đây là range add + range sum. Code chưa có lệnh gán cả đoạn, nhân đoạn hoặc cộng cấp số cộng. Nguồn và phần luyện có các biến thể đó để học tiếp; không coi một hàm add giá trị hằng đã giải được mọi loại cập nhật.

Hợp nhãn là phần toán học của lazy

Với hai phép cộng, chỉ cộng nhãn. Nhưng nếu trước gán thành 5 rồi cộng 2, kết quả là gán thành 7; nếu trước cộng 2 rồi gán thành 5, kết quả là 5. Thứ tự này không thể biểu diễn bằng một tag cộng duy nhất mà giữ mọi thông tin.

Một cách tổng quát hơn là coi cập nhật như hàm biến đổi x thành a·x+b. Hợp hàm cần đúng thứ tự; tổng đoạn đổi thành a·sum+b·len. Đây là hướng suy nghĩ cho một số biến thể, nhưng vẫn phải kiểm kiểu số, modulo và những thao tác thật sự được đề cho. Không phải mọi thay đổi, chẳng hạn lấy căn bậc hai từng phần tử, đều tác động gọn lên một Node chỉ giữ tổng.

Với cộng cấp số cộng, phần tăng phụ thuộc vị trí, nên nhãn phải giữ nhiều thông tin hơn một hằng. Khi đẩy sang hai con, cần dùng đúng tọa độ hoặc độ lệch để con phải nhận cấp số bắt đầu phù hợp. Đó là bài nâng cao trong phần luyện, không chỉ thay value bằng một cặp rồi bỏ qua ý nghĩa vị trí.

Độ phức tạp và cấu trúc khác

Dựng cây O(n), bộ nhớ O(n) với cách cấp phát khoảng 4n. Mỗi cập nhật hoặc truy vấn một đoạn cần O(log n) khi apply, push và hợp nhãn có chi phí hằng. Các nút nằm kín giữa đoạn được xử lý nguyên khối, còn phân nhánh chỉ tiếp tục dọc vùng biên.

Nếu mỗi lần push lại đi qua toàn bộ lá, bạn đã mất lợi ích của nhãn. Nếu Node hoặc tag chứa danh sách dài và thao tác gộp không hằng, phải tính thêm chi phí đó, không giữ nguyên cận O(log n) chỉ vì cây có chiều cao logarit.

Range add + range sum cũng có thể thực hiện bằng hai Fenwick với công thức phù hợp. Lazy Segment Tree linh hoạt hơn cho nhiều tổ hợp thống kê và cập nhật, nhưng cần thiết kế nhãn cẩn thận hơn. Chọn cấu trúc theo loại thao tác thật sự trong đề.

Kiểm với mảng thường và cập nhật chồng lấn

Để tự kiểm tra Lazy Propagation trên dữ liệu nhỏ, bạn hãy giữ thêm một mảng thường, thực hiện cộng trực tiếp vào từng phần tử trong [l, r) và quét tổng đoạn để đối chiếu sau mỗi thao tác. Hãy thử cập nhật đoạn rỗng, cập nhật toàn mảng, các đoạn lồng nhau hoặc giao nhau một phần và cập nhật với số âm xen kẽ truy vấn.

Tự thử cộng toàn mảng rồi hỏi một điểm để bắt lỗi quên push. Tiếp theo cộng một đoạn con rồi hỏi toàn mảng để bắt lỗi quên pull. Cộng +x rồi −x trên cùng đoạn để kiểm hợp nhãn và việc xóa tag cha sau truyền. Chỉ hỏi lại đúng đoạn vừa phủ kín có thể không phát hiện dữ liệu con còn sai.

Luyện ngay trên Big-O Coding

Bài cộng đoạn và hỏi tổng luyện đúng code cơ bản. Bài gán/cộng/đảo yêu cầu thiết kế quy tắc hợp nhãn đa thao tác. Bài cộng cấp số cộng mở rộng nhãn theo vị trí; hãy tự viết tác động lên tổng đoạn và cách truyền xuống hai con trước khi thêm lệnh vào chương trình.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Segment Tree, range updates
• CSES: Range Updates and Sums
• C++ reference: numeric_limits