Cập nhật đoạn cộng

Hướng tiếp cận

Bài toán yêu cầu cập nhật cộng giá trị $v$ trên một đoạn $[l,r]$ nhiều lần, rồi truy vấn mảng cuối cùng. Cách làm ngây thơ duyệt từng phần tử cho mỗi cập nhật có độ phức tạp $O(n·m)$, không khả thi với $n,m$ tới $2·{10}^5$ ($4·{10}^{10}$ phép cộng).

Nhận xét quan trọng

Khi chỉ cần kết quả cuối cùng (offline, không có truy vấn xen kẽ), ta dùng mảng hiệu (difference array): nếu $d$ là mảng hiệu của $a$ với $d_1=a_1$ và $d_i=a_i-a_{i-1}$ thì cập nhật cộng $v$ vào đoạn $[l,r]$ tương đương với:

Sau khi xử lý hết tất cả cập nhật trong $O(1)$ mỗi cái, ta lấy tổng tiền tố (prefix sum) của $d$ để khôi phục $a$.

Thuật toán

1. Khởi tạo mảng $d[1..n+1]$ toàn $0$ (kiểu long long).
2. Với mỗi cập nhật $(l,r,v)$: , .
3. Tính tổng tiền tố: $a_i=a_{i-1}+d_i$ với $a_0=0$.
4. In ra $a_1,a_2,\dots ,a_n$.

Độ phức tạp

• Thời gian: $O(n+m)$.
• Bộ nhớ: $O(n)$.

Lưu ý dùng long long vì tổng giá trị có thể đạt cỡ $m·max|v|\approx 2·{10}^{14}$, vượt phạm vi int 32-bit.