Đăng nhập để tham gia lộ trình luyện tập

Lộ trình Prefix Sum — Tổng tiền tố từ cơ bản đến nâng cao

Giới thiệu

Prefix Sum — Tổng tiền tố là một trong những kỹ thuật nền tảng quan trọng nhất trong lập trình thi đấu.

Ý tưởng cốt lõi là:

Thay vì tính lại thông tin trên một đoạn nhiều lần, ta tính trước thông tin của các tiền tố và sử dụng hiệu giữa hai tiền tố để trả lời nhanh.

Từ một công thức rất đơn giản:

$$P_i=P_{i-1}+a_i$$

ta có thể phát triển thành nhiều kỹ thuật:

• tổng đoạn một chiều;
• đếm phần tử theo đoạn;
• XOR tiền tố;
• prefix theo modulo;
• đếm đoạn con có tổng cho trước;
• đếm đoạn con chia hết;
• tổng đoạn trên ma trận;
• tổng trên khối ba chiều;
• Difference Array;
• Imos Method;
• nhiều lớp Difference Array;
• Prefix Sum của Prefix Sum;
• Prefix Sum kết hợp Binary Search;
• Prefix Sum kết hợp Coordinate Compression;
• Prefix Sum kết hợp Fenwick Tree;
• Prefix Sum kết hợp Monotonic Queue.

Serie này được xây dựng nhằm giúp người học hiểu Prefix Sum như một mô hình tư duy, thay vì chỉ ghi nhớ một công thức.

---

1. Tổng tiền tố một chiều

Cho dãy:

$$a_1,a_2,\ldots,a_n$$

Định nghĩa:

$$P_0=0$$

và:

$$P_i=a_1+a_2+\cdots+a_i$$

Ta có công thức truy hồi:

$$P_i=P_{i-1}+a_i$$

với:

$$1\le i\le n$$

Khi đó tổng đoạn:

$$a_l+a_{l+1}+\cdots+a_r$$

được tính bằng:

$$\boxed{\operatorname{sum}(l,r)=P_r-P_{l-1}}$$

Đây là công thức nền tảng nhất của toàn bộ chuyên đề.

---

2. Vì sao công thức tổng đoạn đúng?

Ta có:

$$P_r=a_1+a_2+\cdots+a_{l-1}+a_l+\cdots+a_r$$

và:

$$P_{l-1}=a_1+a_2+\cdots+a_{l-1}$$

Lấy hiệu:

$$P_r-P_{l-1}$$

thì phần:

$$a_1+a_2+\cdots+a_{l-1}$$

bị triệt tiêu.

Còn lại:

$$a_l+a_{l+1}+\cdots+a_r$$

Do đó:

$$\boxed{\operatorname{sum}(l,r)=P_r-P_{l-1}}$$

---

3. Độ phức tạp

Nếu mỗi truy vấn tự cộng từ $l$ đến $r$, một truy vấn có thể tốn:

$$O(n)$$

Với $q$ truy vấn:

$$O(nq)$$

Sau khi xây Prefix Sum:

$$O(n)$$

mỗi truy vấn chỉ còn:

$$O(1)$$

Tổng:

$$\boxed{O(n+q)}$$

Đây là cải tiến quan trọng khi số lượng truy vấn lớn.

---

4. Quy tắc dùng $P_0=0$

Việc đặt:

$$P_0=0$$

giúp công thức:

$$P_r-P_{l-1}$$

đúng cả khi:

$$l=1$$

Khi đó:

$$P_r-P_0=P_r$$

Không cần xử lý riêng đoạn bắt đầu từ phần tử đầu tiên.

---

5. Prefix Sum trên dãy sau khi sắp xếp

Một số bài yêu cầu đồng thời:

• tổng trên dãy ban đầu;
• tổng trên dãy đã sắp xếp.

Ta xây hai mảng:

$$P_i=a_1+a_2+\cdots+a_i$$

và sau khi sắp xếp:

$$b_1\le b_2\le\cdots\le b_n$$

xây:

$$S_i=b_1+b_2+\cdots+b_i$$

Khi đó:

$$\operatorname{sumOriginal}(l,r)=P_r-P_{l-1}$$

và:

$$\operatorname{sumSorted}(l,r)=S_r-S_{l-1}$$

Một bài toán có thể cần nhiều hệ Prefix Sum khác nhau trên cùng dữ liệu.

---

6. Prefix Count — Đếm bằng tổng tiền tố

Prefix Sum không nhất thiết phải cộng chính giá trị $a_i$.

Ta có thể biến mỗi phần tử thành:

$$b_i= \begin{cases} 1 & \text{nếu } a_i \text{ thỏa điều kiện}\\ 0 & \text{ngược lại} \end{cases}$$

Sau đó:

$$P_i=P_{i-1}+b_i$$

Khi đó:

$$P_r-P_{l-1}$$

chính là số phần tử thỏa điều kiện trong đoạn $[l,r]$.

Đây là Prefix Count.

---

7. Đếm nhiều loại phần tử

Giả sử mỗi phần tử thuộc một trong $k$ loại.

Ta có thể xây:

$$P_{c,i}$$

là số phần tử thuộc loại $c$ trong:

$$[1,i]$$

Công thức:

$$P_{c,i} = P_{c,i-1} + [a_i=c]$$

Trong đó:

$$[\text{điều kiện}] = \begin{cases} 1 & \text{nếu điều kiện đúng}\\ 0 & \text{nếu điều kiện sai} \end{cases}$$

Số phần tử loại $c$ trong $[l,r]$:

$$\boxed{P_{c,r}-P_{c,l-1}}$$

---

8. Prefix trên quan hệ giữa hai phần tử liên tiếp

Không phải lúc nào trạng thái tại vị trí $i$ chỉ phụ thuộc vào $a_i$.

Ví dụ cần đếm số vị trí:

$$i$$

sao cho:

$$s_i=s_{i+1}$$

Ta định nghĩa:

$$b_i= \begin{cases} 1 & \text{nếu } s_i=s_{i+1}\\ 0 & \text{ngược lại} \end{cases}$$

Sau đó xây:

$$P_i=P_{i-1}+b_i$$

Với truy vấn trên đoạn ký tự $[l,r]$, chỉ xét các cặp:

$$(l,l+1),(l+1,l+2),\ldots,(r-1,r)$$

nên kết quả là:

$$\boxed{P_{r-1}-P_{l-1}}$$

Dạng này nhấn mạnh rằng:

Prefix Sum có thể được xây trên một dãy đặc trưng được tạo ra từ dữ liệu gốc.

---

9. Prefix đếm một mẫu ngắn trong chuỗi

Giả sử cần đếm số lần chuỗi "AC" xuất hiện hoàn toàn trong đoạn $[l,r]$.

Định nghĩa:

$$b_i= \begin{cases} 1 & \text{nếu } s_i=A \text{ và } s_{i+1}=C\\ 0 & \text{ngược lại} \end{cases}$$

Sau đó:

$$P_i=P_{i-1}+b_i$$

Kết quả truy vấn:

$$\boxed{P_{r-1}-P_{l-1}}$$

Đây là dạng tổng quát của Prefix Sum trên sự kiện cục bộ.

---

10. Prefix XOR

Phép XOR cũng có tính chất triệt tiêu:

$$x\oplus x=0$$

và:

$$x\oplus0=x$$

Ta định nghĩa:

$$X_0=0$$ $$X_i=X_{i-1}\oplus a_i$$

Khi đó XOR của đoạn $[l,r]$ là:

$$\boxed{X_r\oplus X_{l-1}}$$

Công thức này tương tự tổng đoạn:

$$P_r-P_{l-1}$$

nhưng phép toán được thay từ cộng sang XOR.

---

11. Góc nhìn đại số của Prefix Sum

Prefix Sum hoạt động tốt khi phép toán có khả năng loại bỏ phần tiền tố trước đó.

Với phép cộng:

$$P_r-P_{l-1}$$

Với XOR:

$$X_r\oplus X_{l-1}$$

Điều quan trọng không phải chỉ là từ khóa “Sum”, mà là khả năng xây thông tin tích lũy và loại bỏ phần không cần thiết.

---

12. Đoạn con và hiệu hai Prefix Sum

Một đoạn con liên tiếp:

$$a_l,a_{l+1},\ldots,a_r$$

có tổng:

$$P_r-P_{l-1}$$

Do đó bài toán về đoạn con thường có thể chuyển thành bài toán về hai Prefix Sum.

Nếu cần:

$$a_l+\cdots+a_r=x$$

thì:

$$P_r-P_{l-1}=x$$

hay:

$$\boxed{P_{l-1}=P_r-x}$$

Đây là phép biến đổi cực kỳ quan trọng.

---

13. Đếm đoạn con có tổng bằng $x$

Ta cần đếm số cặp:

$$0\le i<j\le n$$

sao cho:

$$P_j-P_i=x$$

Tương đương:

$$P_i=P_j-x$$

Khi đang xét $P_j$, ta cần biết trước đó có bao nhiêu Prefix Sum bằng:

$$P_j-x$$

Nếu:

$$\operatorname{cnt}[v]$$

là số Prefix Sum trước đó có giá trị $v$, số đoạn mới kết thúc tại $j$ là:

$$\boxed{\operatorname{cnt}[P_j-x]}$$

Sau đó tăng:

$$\operatorname{cnt}[P_j]$$

---

14. Prefix Sum ban đầu phải được tính là một trạng thái

Ta luôn có:

$$P_0=0$$

Do đó ban đầu cần xem giá trị $0$ đã xuất hiện một lần:

$$\operatorname{cnt}[0]=1$$

Điều này cho phép đếm các đoạn bắt đầu từ vị trí $1$.

Ví dụ nếu:

$$P_j=x$$

thì:

$$P_j-P_0=x$$

tương ứng đoạn:

$$[1,j]$$

---

15. Đếm đoạn con có tổng chia hết cho $m$

Ta cần:

$$P_r-P_l\equiv0\pmod m$$

Tương đương:

$$\boxed{P_r\equiv P_l\pmod m}$$

Như vậy hai Prefix Sum có cùng phần dư sẽ tạo thành một đoạn có tổng chia hết cho $m$.

Nếu có:

$$c_r$$

Prefix Sum mang phần dư $r$, số cặp chọn được là:

$$\binom{c_r}{2}$$

Do đó:

$$\boxed{ \text{answer} = \sum_{r=0}^{m-1} \binom{c_r}{2} }$$

với:

$$\binom{x}{2} = \frac{x(x-1)}{2}$$

---

16. Chuẩn hóa modulo khi có số âm

Trong nhiều ngôn ngữ, nếu $P_i$ âm thì:

$$P_i\bmod m$$

có thể nhận giá trị âm.

Để chuẩn hóa:

$$\boxed{ r=((P_i\bmod m)+m)\bmod m }$$

Khi đó:

$$0\le r<m$$

---

17. Tìm đoạn dài nhất có tổng chia hết cho $m$

Nếu:

$$P_i\equiv P_j\pmod m$$

thì đoạn:

$$[i+1,j]$$

có tổng chia hết cho $m$.

Độ dài:

$$j-i$$

Để tối đa hóa độ dài, với mỗi phần dư $r$, chỉ cần nhớ:

• vị trí xuất hiện đầu tiên;
• vị trí xuất hiện cuối cùng.

Nếu:

$$first[r]$$

và:

$$last[r]$$

là hai vị trí đó thì ứng viên:

$$\boxed{last[r]-first[r]}$$

---

18. Prefix Sum sau khi biến đổi dữ liệu

Nhiều bài không sử dụng trực tiếp:

$$P_i=a_1+\cdots+a_i$$

mà trước tiên biến đổi $a_i$.

Ví dụ với dãy chữ số:

$$d_1,d_2,\ldots,d_n$$

Nếu một đoạn có độ dài bằng tổng chữ số:

$$d_l+\cdots+d_r=r-l+1$$

chuyển vế:

$$(d_l-1)+(d_{l+1}-1)+\cdots+(d_r-1)=0$$

Đặt:

$$b_i=d_i-1$$

Bài toán trở thành:

Đếm số đoạn của $b$ có tổng bằng $0$.

Hoặc với Prefix Sum:

$$S_i=d_1+d_2+\cdots+d_i$$

ta có:

$$S_r-S_{l-1}=r-l+1$$

suy ra:

$$S_r-r=S_{l-1}-(l-1)$$

Đặt:

$$Q_i=S_i-i$$

Bài toán trở thành đếm các cặp Prefix Sum biến đổi bằng nhau.

Đây là một kỹ thuật rất mạnh:

Biến đổi điều kiện của đoạn thành quan hệ giữa hai trạng thái tiền tố.

---

19. Chia dãy thành ba phần có tổng bằng nhau

Giả sử tổng toàn dãy:

$$S=P_n$$

Muốn chia thành ba đoạn liên tiếp có tổng bằng nhau.

Điều kiện cần:

$$S\equiv0\pmod3$$

Đặt:

$$T=\frac{S}{3}$$

Điểm chia thứ nhất $i$ phải thỏa:

$$P_i=T$$

Điểm chia thứ hai $j$ phải thỏa:

$$P_j=2T$$

với:

$$i<j<n$$

Khi duyệt $j$, ta chỉ cần biết số lượng vị trí $i<j$ đã có:

$$P_i=T$$

Mỗi vị trí $j$ với:

$$P_j=2T$$

đóng góp số điểm chia thứ nhất hợp lệ trước nó.

---

20. Maximum Subarray Sum bằng Prefix Sum

Tổng đoạn:

$$[l,r]$$

là:

$$P_r-P_{l-1}$$

Với $r$ cố định, muốn tổng lớn nhất thì cần:

$$P_{l-1}$$

nhỏ nhất.

Do đó:

$$\boxed{ \max_{1\le l\le r} (P_r-P_{l-1}) = P_r-\min_{0\le j<r}P_j }$$

Duyệt $r$ từ trái sang phải và duy trì Prefix Sum nhỏ nhất đã thấy.

Đây là một cách nhìn rất quan trọng của bài toán Maximum Subarray.

---

21. Đoạn con có giới hạn độ dài

Giả sử cần đoạn:

$$[l,r]$$

với độ dài:

$$A\le r-l+1\le B$$

Đặt:

$$i=l-1$$

Khi đó:

$$A\le r-i\le B$$

suy ra:

$$r-B\le i\le r-A$$

Tổng đoạn:

$$P_r-P_i$$

Với $r$ cố định, cần tìm Prefix Sum nhỏ nhất:

$$\min P_i$$

trong cửa sổ chỉ số:

$$[r-B,r-A]$$

Do đó:

$$\boxed{ answer = \max_r \left( P_r- \min_{r-B\le i\le r-A}P_i \right) }$$

Đây là nền tảng để kết hợp Prefix Sum với cấu trúc duy trì minimum động.

---

22. Đoạn ngắn nhất có tổng ít nhất $K$

Ta cần:

$$P_j-P_i\ge K$$

tương đương:

$$P_i\le P_j-K$$

Mục tiêu là tối thiểu:

$$j-i$$

Khác với trường hợp các số đều dương, khi có số âm ta không thể dùng cửa sổ trượt thông thường.

Prefix Sum giúp biến bài toán thành:

Với mỗi $j$, tìm chỉ số $i$ càng lớn càng tốt nhưng vẫn thỏa $P_i\le P_j-K$.

Các Prefix Sum ứng viên có thể được duy trì theo thứ tự đơn điệu.

---

23. Đếm đoạn có tổng nhỏ hơn một giá trị

Ta cần đếm:

$$P_j-P_i<t$$

suy ra:

$$P_i>P_j-t$$

Như vậy bài toán trở thành:

Với mỗi Prefix Sum $P_j$, đếm số Prefix Sum trước đó lớn hơn một ngưỡng.

Đây là cầu nối từ Prefix Sum sang:

• Coordinate Compression;
• Fenwick Tree;
• Ordered Data Structure.

---

24. Prefix Maximum kết hợp Prefix Sum

Trong một số bài, một truy vấn cho giới hạn $x$ và ta cần lấy tiền tố dài nhất sao cho mọi phần tử trong đó không vượt quá $x$.

Định nghĩa:

$$M_i=\max(a_1,a_2,\ldots,a_i)$$

Ta có:

$$M_1\le M_2\le\cdots\le M_n$$

Đồng thời xây:

$$P_i=a_1+a_2+\cdots+a_i$$

Tìm vị trí lớn nhất $k$ sao cho:

$$M_k\le x$$

Khi đó đáp án là:

$$\boxed{P_k}$$

Đây là dạng kết hợp:

$$\text{Prefix Maximum} + \text{Prefix Sum} + \text{Binary Search}$$

---

25. Prefix Sum hai chiều

Cho ma trận:

$$a_{i,j}$$

với:

$$1\le i\le n$$ $$1\le j\le m$$

Định nghĩa:

$$P_{i,j}$$

là tổng hình chữ nhật từ:

$$(1,1)$$

đến:

$$(i,j)$$

Công thức:

$$\boxed{ P_{i,j} = a_{i,j} + P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1} }$$

---

26. Vì sao Prefix Sum 2D phải cộng rồi trừ?

Khi cộng:

$$P_{i-1,j} + P_{i,j-1}$$

vùng:

$$P_{i-1,j-1}$$

đã bị tính hai lần.

Do đó phải trừ một lần:

$$-P_{i-1,j-1}$$

Đây chính là nguyên lý Inclusion-Exclusion.

---

27. Tổng hình chữ nhật

Xét hình chữ nhật:

$$x_1\le i\le x_2$$ $$y_1\le j\le y_2$$

Tổng là:

$$\boxed{ P_{x_2,y_2} - P_{x_1-1,y_2} - P_{x_2,y_1-1} + P_{x_1-1,y_1-1} }$$

Ta:

• lấy hình chữ nhật lớn;
• trừ vùng phía trên;
• trừ vùng bên trái;
• cộng lại góc bị trừ hai lần.

---

28. Prefix Count 2D

Nếu ma trận chỉ cần đếm các ô thỏa điều kiện, đặt:

$$b_{i,j} = \begin{cases} 1 & \text{nếu ô }(i,j)\text{ thỏa điều kiện}\\ 0 & \text{ngược lại} \end{cases}$$

Sau đó xây Prefix Sum 2D trên $b$.

Khi đó truy vấn hình chữ nhật trả về số ô thỏa điều kiện trong:

$$O(1)$$

---

29. Ma trận ngưỡng

Một kỹ thuật rất quan trọng là với một giá trị thử $x$, biến ma trận thành ma trận nhị phân.

Ví dụ:

$$b_{i,j} = \begin{cases} 1 & \text{nếu } a_{i,j}>x\\ 0 & \text{ngược lại} \end{cases}$$

Prefix Sum 2D cho phép nhanh chóng đếm số phần tử lớn hơn $x$ trong mọi hình vuông.

Nhờ đó ta có thể kiểm tra một điều kiện theo $x$.

Nếu điều kiện có tính đơn điệu, có thể kết hợp với Binary Search.

Đây là dạng:

$$\boxed{ \text{Binary Search on Answer} + \text{2D Prefix Sum} }$$

---

30. Median trong một vùng

Một vùng có:

$$K^2$$

phần tử.

Để kiểm tra một giá trị $x$ có thể là cận cho trung vị hay không, ta có thể đếm số phần tử:

$$>x$$

hoặc:

$$\le x$$

trong từng hình vuông $K\times K$.

Nếu biến mỗi phần tử thành $0/1$, mỗi lần kiểm tra chỉ còn là truy vấn tổng hình chữ nhật.

Đây là một ví dụ điển hình cho việc:

Prefix Sum không trực tiếp tìm đáp án, nhưng làm cho hàm kiểm tra của Binary Search trở nên đủ nhanh.

---

31. Prefix Sum trên các cặp đầu mút

Một đoạn có thể được biểu diễn bằng hai đầu mút:

$$(l,r)$$

Ta có thể xây ma trận:

$$A_{l,r}$$

biểu diễn số đối tượng có chính xác cặp đầu mút $(l,r)$.

Sau đó xây Prefix Sum 2D.

Một truy vấn yêu cầu:

$$L\le l\le r\le R$$

có thể chuyển thành truy vấn một miền trong mặt phẳng chỉ số.

Đây là cách biến bài toán interval thành bài toán 2D Prefix Sum.

---

32. Coordinate Compression kết hợp Prefix 2D

Nếu tọa độ rất lớn nhưng chỉ có $n$ điểm quan trọng, ta có thể sắp xếp các tọa độ và thay chúng bằng hạng:

$$1,2,\ldots,n$$

Sau khi nén tọa độ, dữ liệu trở thành một lưới nhỏ hơn.

Ta có thể xây:

$$P_{i,j}$$

trên lưới đó.

Một hình chữ nhật tọa độ ban đầu trở thành truy vấn hình chữ nhật trên chỉ số đã nén.

Dạng này thường xuất hiện trong các bài:

• đếm điểm;
• đếm hình chữ nhật;
• chọn hai biên;
• kết hợp đếm số phần tử bên trong.

---

33. Prefix Sum ba chiều

Cho khối:

$$a_{x,y,z}$$

Định nghĩa:

$$P_{x,y,z}$$

là tổng trong khối:

$$[1,x]\times[1,y]\times[1,z]$$

Theo Inclusion-Exclusion:

$$\boxed{ \begin{aligned} P_{x,y,z} ={}&a_{x,y,z} +P_{x-1,y,z} +P_{x,y-1,z} +P_{x,y,z-1}\\ &-P_{x-1,y-1,z} -P_{x-1,y,z-1} -P_{x,y-1,z-1}\\ &+P_{x-1,y-1,z-1} \end{aligned} }$$

---

34. Tổng một hình hộp

Cần tính tổng trong:

$$[x_1,x_2] \times [y_1,y_2] \times [z_1,z_2]$$

Đặt:

$$F(x,y,z)=P_{x,y,z}$$

Kết quả:

$$\begin{aligned} S={}& F(x_2,y_2,z_2)\\ &-F(x_1-1,y_2,z_2) -F(x_2,y_1-1,z_2) -F(x_2,y_2,z_1-1)\\ &+F(x_1-1,y_1-1,z_2) +F(x_1-1,y_2,z_1-1) +F(x_2,y_1-1,z_1-1)\\ &-F(x_1-1,y_1-1,z_1-1) \end{aligned}$$

Đây là Inclusion-Exclusion trong ba chiều.

---

35. Quy luật Inclusion-Exclusion nhiều chiều

Trong một chiều:

$$+ -$$

Trong hai chiều:

$$+ - - +$$

Trong ba chiều:

$$+ - - - + + + -$$

Dấu phụ thuộc vào số chiều bị dịch về biên trước.

Có thể hiểu bằng công thức:

$$(-1)^k$$

với $k$ là số tọa độ dùng biên trái trừ $1$.

---

36. Difference Array — Mảng hiệu

Prefix Sum thường dùng cho:

nhiều truy vấn đọc trên dữ liệu tĩnh.

Difference Array thường dùng cho:

nhiều cập nhật đoạn rồi mới cần dữ liệu cuối cùng.

Cho dãy:

$$a_1,a_2,\ldots,a_n$$

Định nghĩa:

$$D_1=a_1$$

và:

$$D_i=a_i-a_{i-1}$$

với:

$$i\ge2$$

Ta có thể khôi phục:

$$a_i=D_1+D_2+\cdots+D_i$$

hay:

$$\boxed{ a_i=\sum_{j=1}^{i}D_j }$$

Như vậy:

Prefix Sum và Difference Array là hai phép biến đổi ngược nhau.

---

37. Cộng $x$ cho cả đoạn $[l,r]$

Muốn:

$$a_i\leftarrow a_i+x$$

với:

$$l\le i\le r$$

ta chỉ cần:

$$D_l\mathrel{+}=x$$

và nếu tồn tại $r+1$:

$$D_{r+1}\mathrel{-}=x$$

Sau tất cả cập nhật, lấy Prefix Sum của $D$ để thu được giá trị thật.

Mỗi cập nhật chỉ mất:

$$O(1)$$

---

38. Vì sao phải trừ tại $r+1$?

Khi cộng:

$$D_l\mathrel{+}=x$$

Prefix Sum từ $l$ trở đi đều tăng $x$.

Nhưng ta chỉ muốn ảnh hưởng đến:

$$[l,r]$$

Do đó tại vị trí:

$$r+1$$

phải hủy hiệu ứng bằng:

$$D_{r+1}\mathrel{-}=x$$

Kết quả:

• trước $l$: không đổi;
• từ $l$ đến $r$: tăng $x$;
• sau $r$: hiệu ứng bị triệt tiêu.

---

39. Difference Array để đếm số lần một vị trí được phủ

Mỗi đoạn:

$$[l,r]$$

đóng góp:

$$+1$$

cho mọi vị trí trong đoạn.

Ta cập nhật:

$$D_l\mathrel{+}=1$$ $$D_{r+1}\mathrel{-}=1$$

Sau khi Prefix Sum:

$$C_i=C_{i-1}+D_i$$

thì:

$$C_i$$

là số đoạn phủ vị trí $i$.

---

40. Tối ưu tổng bằng số lần xuất hiện

Giả sử vị trí $i$ được sử dụng:

$$c_i$$

lần.

Tổng đóng góp:

$$\sum_{i=1}^{n}a_ic_i$$

Nếu có quyền hoán vị các giá trị $a_i$, để tối đa tổng ta sắp:

$$a_1\le a_2\le\cdots\le a_n$$

và:

$$c_1\le c_2\le\cdots\le c_n$$

rồi ghép cùng thứ tự:

$$\boxed{ \sum_{i=1}^{n}a_ic_i }$$

Đây là sự kết hợp:

$$\text{Difference Array} + \text{Sorting}$$

---

41. Hai lớp Difference Array

Có những bài có:

• $n$ phần tử;
• $m$ phép cập nhật;
• $q$ truy vấn, mỗi truy vấn yêu cầu thực hiện một đoạn các phép cập nhật.

Giả sử phép cập nhật thứ $i$ tác động lên:

$$[l_i,r_i]$$

với giá trị:

$$d_i$$

Trước tiên cần tính số lần mỗi phép cập nhật được thực hiện.

Dùng Difference Array trên chỉ số phép toán:

$$opDiff_x\mathrel{+}=1$$ $$opDiff_{y+1}\mathrel{-}=1$$

Sau Prefix Sum:

$$cnt_i$$

là số lần phép cập nhật thứ $i$ được thực hiện.

Khi đó phép thứ $i$ thực sự cộng:

$$cnt_i\cdot d_i$$

vào đoạn:

$$[l_i,r_i]$$

Tiếp tục dùng Difference Array thứ hai trên dãy ban đầu.

Đây là:

$$\boxed{\text{Difference of operations}+\text{Difference of array}}$$

---

42. Difference Array hai chiều

Muốn cộng $v$ cho toàn bộ hình chữ nhật:

$$[x_1,x_2]\times[y_1,y_2]$$

ta cập nhật bốn góc:

$$D_{x_1,y_1}\mathrel{+}=v$$ $$D_{x_2+1,y_1}\mathrel{-}=v$$ $$D_{x_1,y_2+1}\mathrel{-}=v$$ $$D_{x_2+1,y_2+1}\mathrel{+}=v$$

Sau tất cả cập nhật, lấy Prefix Sum hai chiều:

$$A_{i,j} = D_{i,j} + A_{i-1,j} + A_{i,j-1} - A_{i-1,j-1}$$

Khi đó $A_{i,j}$ là tổng tác động tại ô $(i,j)$.

---

43. Imos Method hai chiều

2D Difference Array thường được gọi là 2D Imos Method.

Ứng dụng:

• phủ nhiều hình chữ nhật;
• tô nhiều vùng;
• đếm số lớp phủ tại mỗi ô;
• tính diện tích được phủ đúng $k$ lần;
• tính diện tích được phủ ít nhất một lần.

Nếu:

$$C_{i,j}$$

là số hình chữ nhật phủ ô $(i,j)$, ta có thể đếm:

$$\#\{(i,j)\mid C_{i,j}=k\}$$

hoặc:

$$\#\{(i,j)\mid C_{i,j}>0\}$$

---

44. Prefix Sum của Prefix Sum

Cho:

$$P_i=\sum_{j=1}^{i}a_j$$

Tiếp tục định nghĩa:

$$Q_i=\sum_{j=1}^{i}P_j$$

Ta gọi $Q$ là Prefix Sum cấp hai.

Khai triển:

$$Q_i = P_1+P_2+\cdots+P_i$$

Mỗi $a_j$ xuất hiện trong:

$$P_j,P_{j+1},\ldots,P_i$$

tổng cộng:

$$i-j+1$$

lần.

Do đó:

$$\boxed{ Q_i = \sum_{j=1}^{i}(i-j+1)a_j }$$

Prefix cấp hai thường xuất hiện khi cần tổng của nhiều tổng đoạn.

---

45. Tổng tất cả Prefix Sum trên một đoạn

Ta có:

$$Q_i=P_1+P_2+\cdots+P_i$$

Khi đó:

$$P_l+P_{l+1}+\cdots+P_r$$

bằng:

$$\boxed{Q_r-Q_{l-1}}$$

Ý tưởng này có thể tiếp tục lên Prefix cấp ba nếu cấu trúc bài yêu cầu.

---

46. Tổng của các đoạn có cùng điểm đầu

Với điểm đầu $l$ cố định:

$$S(l,r)=P_r-P_{l-1}$$

Tổng các đoạn:

$$[l,l],[l,l+1],\ldots,[l,r]$$

là:

$$\sum_{j=l}^{r}(P_j-P_{l-1})$$

Suy ra:

$$\sum_{j=l}^{r}P_j-(r-l+1)P_{l-1}$$

Dùng Prefix cấp hai:

$$\sum_{j=l}^{r}P_j=Q_r-Q_{l-1}$$

nên:

$$\boxed{ \sum_{j=l}^{r}S(l,j) = Q_r-Q_{l-1} - (r-l+1)P_{l-1} }$$

Đây là một công thức quan trọng trong các bài tổng của nhiều subarray sum.

---

47. Tổng mọi đoạn con của một dãy

Mỗi phần tử $a_i$ xuất hiện trong bao nhiêu đoạn con?

Điểm đầu có thể chọn:

$$1,2,\ldots,i$$

nên có:

$$i$$

cách.

Điểm cuối có thể chọn:

$$i,i+1,\ldots,n$$

nên có:

$$n-i+1$$

cách.

Do đó $a_i$ xuất hiện trong:

$$i(n-i+1)$$

đoạn.

Tổng tất cả tổng đoạn con là:

$$\boxed{ \sum_{i=1}^{n} a_i\cdot i\cdot(n-i+1) }$$

Đây là một cách nhìn đóng góp thay cho việc liệt kê mọi đoạn.

---

48. Flatten các tổng đoạn con

Một số bài sắp các tổng đoạn theo thứ tự:

$$[1,1],[1,2],\ldots,[1,n], [2,2],[2,3],\ldots$$

Nhóm bắt đầu tại $l$ có:

$$n-l+1$$

phần tử.

Số phần tử trước nhóm $l$ là:

$$\sum_{i=1}^{l-1}(n-i+1)$$

Khai triển:

$$(l-1)(n+1)-\frac{(l-1)l}{2}$$

Do đó vị trí bắt đầu của nhóm $l$ trong dãy phẳng có thể được xác định bằng công thức Prefix theo số lượng.

Sau khi xác định nhóm chứa một vị trí, tổng một phần nhóm có thể được tính bằng Prefix cấp hai.

Đây là dạng Prefix Sum nâng cao:

$$\boxed{ \text{Prefix trên số lượng} + \text{Prefix trên giá trị} + \text{Prefix cấp hai} }$$

---

49. Prefix Sum và Binary Search

Nếu có hàm Prefix đơn điệu:

$$P_1\le P_2\le\cdots\le P_n$$

ta có thể tìm vị trí đầu tiên hoặc cuối cùng thỏa điều kiện bằng Binary Search.

Ví dụ tìm lớn nhất $k$ sao cho:

$$P_k\le x$$

hoặc nhỏ nhất $k$ sao cho:

$$P_k\ge x$$

Lưu ý:

Prefix Sum chỉ đơn điệu nếu dữ liệu cộng vào không âm.

Nếu có số âm:

$$P_i$$

không nhất thiết tăng.

---

50. Prefix Sum và Two Pointers

Nếu:

$$a_i>0$$

thì khi mở rộng đầu phải $r$, tổng cửa sổ không giảm.

Điều này cho phép dùng Two Pointers cho các điều kiện như:

$$\sum_{i=l}^{r}a_i=x$$

hoặc:

$$\sum_{i=l}^{r}a_i\le x$$

Prefix Sum vẫn giúp hiểu bản chất:

$$P_r-P_{l-1}$$

nhưng tính đơn điệu của dữ liệu dương cho phép xử lý nhanh hơn bằng hai con trỏ.

Nếu có số âm, tính đơn điệu này biến mất.

---

51. Prefix Sum và Coordinate Compression

Các Prefix Sum:

$$P_0,P_1,\ldots,P_n$$

có thể rất lớn hoặc âm.

Nếu cần đưa chúng vào Fenwick Tree hoặc một cấu trúc dựa trên chỉ số, ta có thể:

1. thu thập tất cả giá trị Prefix Sum;
2. sắp xếp;
3. loại bỏ giá trị trùng;
4. thay mỗi giá trị bằng thứ hạng.

Nếu:

$$v_1<v_2<\cdots<v_k$$

thì ánh xạ:

$$v_i\rightarrow i$$

Bản chất thứ tự vẫn được bảo toàn.

---

52. Prefix Sum và Fenwick Tree

Prefix Sum tĩnh trả lời:

$$\operatorname{sum}(1,i)$$

rất nhanh nhưng khó xử lý cập nhật.

Fenwick Tree mở rộng ý tưởng Prefix Sum sang dữ liệu động.

Hai thao tác cơ bản:

• cập nhật một vị trí;
• lấy tổng tiền tố.

Nếu:

$$query(i)=a_1+\cdots+a_i$$

thì tổng đoạn vẫn là:

$$\boxed{ query(r)-query(l-1) }$$

Điểm khác biệt là dữ liệu có thể thay đổi giữa các truy vấn.

---

53. Static Prefix Sum và Dynamic Prefix Sum

Nếu dữ liệu không thay đổi:

$$\boxed{\text{Prefix Sum}}$$

thường là lựa chọn đơn giản nhất.

Xây dựng:

$$O(n)$$

Truy vấn:

$$O(1)$$

Nếu có cập nhật điểm:

$$\boxed{\text{Fenwick Tree hoặc Segment Tree}}$$

thường phù hợp hơn.

Cập nhật:

$$O(\log n)$$

Truy vấn:

$$O(\log n)$$

Đây là bước phát triển tự nhiên từ Static Range Sum sang Dynamic Range Sum.

---

54. Sai lầm thường gặp — lệch chỉ số

Công thức chuẩn:

$$P_i=a_1+\cdots+a_i$$

và:

$$\operatorname{sum}(l,r)=P_r-P_{l-1}$$

Sai phổ biến:

$$P_r-P_l$$

Công thức này làm mất phần tử $a_l$.

---

55. Sai lầm thường gặp — quên $P_0$

Nếu không có:

$$P_0=0$$

các đoạn bắt đầu tại:

$$l=1$$

phải xử lý riêng.

Nên luôn tạo trạng thái Prefix rỗng:

$$\boxed{P_0=0}$$

---

56. Sai lầm thường gặp — overflow

Nếu:

$$|a_i|\le10^9$$

và:

$$n\le2\cdot10^5$$

thì tổng có thể đạt khoảng:

$$2\cdot10^{14}$$

vượt giới hạn số nguyên 32-bit.

Trong C++ nên dùng:

$$\texttt{long long}$$

cho:

• Prefix Sum;
• đáp án;
• tích số;
• số lượng cặp lớn.

---

57. Sai lầm thường gặp — dùng Prefix Sum khi dữ liệu thay đổi

Prefix Sum tĩnh giả sử:

$$a_i$$

không thay đổi sau khi xây mảng.

Nếu một phần tử thay đổi, tất cả:

$$P_i$$

phía sau vị trí đó đều thay đổi.

Do đó nếu có nhiều cập nhật xen kẽ truy vấn, cần chuyển sang cấu trúc động.

---

58. Sai lầm thường gặp — modulo âm

Không nên chỉ dùng:

$$P_i\bmod m$$

nếu $P_i$ có thể âm.

Nên chuẩn hóa:

$$\boxed{ ((P_i\bmod m)+m)\bmod m }$$

---

59. Sai lầm thường gặp — nhầm Prefix Sum và Sliding Window

Prefix Sum:

• dùng được với số âm;
• cho phép truy vấn đoạn bất kỳ;
• không yêu cầu cửa sổ đơn điệu.

Sliding Window thường cần một tính đơn điệu nhất định.

Ví dụ với dãy số dương, tổng cửa sổ tăng khi mở rộng sang phải.

Nhưng khi có số âm, tính chất này không còn đúng.

---

60. Sai lầm thường gặp — Prefix Sum 2D thiếu góc cộng lại

Công thức đúng:

$$P_{i,j} = a_{i,j} + P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1}$$

Và truy vấn:

$$P_{x_2,y_2} - P_{x_1-1,y_2} - P_{x_2,y_1-1} + P_{x_1-1,y_1-1}$$

Dấu cộng cuối cùng là bắt buộc vì vùng giao đã bị trừ hai lần.

---

61. Sai lầm thường gặp — Difference Array quên điểm kết thúc

Cập nhật đoạn:

$$[l,r]$$

phải gồm:

$$D_l\mathrel{+}=x$$

và:

$$D_{r+1}\mathrel{-}=x$$

nếu $r+1$ còn trong miền chỉ số.

Nếu chỉ cộng ở $l$, tác động sẽ kéo dài đến cuối mảng.

---

62. Mô hình tư duy tổng quát

Khi gặp bài toán đoạn, hãy thử đặt:

$$P_i=\text{thông tin của tiền tố }[1,i]$$

Sau đó hỏi:

Thông tin của $[l,r]$ có thể được suy ra từ hai tiền tố $[1,r]$ và $[1,l-1]$ hay không?

Nếu có, Prefix Sum có thể là hướng phù hợp.

---

63. Mô hình biến đổi đoạn con

Nếu đề cho điều kiện:

$$f(a_l,\ldots,a_r)$$

hãy thử viết lại bằng Prefix:

$$F(r)-F(l-1)$$

Sau đó chuyển điều kiện thành:

$$F(l-1)=g(F(r))$$

hoặc:

$$F(l-1)<g(F(r))$$

hoặc:

$$F(l-1)\equiv F(r)\pmod m$$

Từ đây bài toán có thể trở thành:

• đếm giá trị bằng nhau;
• đếm giá trị nhỏ hơn;
• tìm minimum;
• tìm maximum;
• tìm phần dư giống nhau.

---

64. Các mô hình công thức cần ghi nhớ

Tổng đoạn

$$\boxed{ \operatorname{sum}(l,r)=P_r-P_{l-1} }$$

XOR đoạn

$$\boxed{ \operatorname{xor}(l,r)=X_r\oplus X_{l-1} }$$

Đoạn có tổng bằng $x$

$$\boxed{ P_r-P_{l-1}=x }$$

hay:

$$\boxed{ P_{l-1}=P_r-x }$$

Đoạn có tổng chia hết cho $m$

$$\boxed{ P_r\equiv P_{l-1}\pmod m }$$

Maximum Subarray

$$\boxed{ P_r-\min_{0\le i<r}P_i }$$

Prefix Sum 2D

$$\boxed{ P_{i,j} = a_{i,j} + P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1} }$$

Rectangle Sum

$$\boxed{ P_{x_2,y_2} - P_{x_1-1,y_2} - P_{x_2,y_1-1} + P_{x_1-1,y_1-1} }$$

Difference Array update

$$\boxed{ D_l\mathrel{+}=x,\qquad D_{r+1}\mathrel{-}=x }$$

Khôi phục Difference Array

$$\boxed{ a_i=a_{i-1}+D_i }$$

Tổng mọi subarray

$$\boxed{ \sum_{i=1}^{n}a_i\,i(n-i+1) }$$

---

65. Các tầng kiến thức trong serie

Serie được sắp xếp theo hướng tăng dần độ khó.

Tầng 1 — Prefix Sum trực tiếp

Mục tiêu:

• hiểu $P_i$;
• truy vấn tổng đoạn;
• làm quen $P_0$;
• tránh lỗi chỉ số.

Công thức chính:

$$P_i=P_{i-1}+a_i$$ $$\operatorname{sum}(l,r)=P_r-P_{l-1}$$

---

Tầng 2 — Prefix Count và Prefix XOR

Mục tiêu:

• hiểu rằng Prefix không chỉ dùng cho phép cộng;
• xây dãy đặc trưng;
• đếm điều kiện trên đoạn;
• XOR đoạn.

---

Tầng 3 — Prefix Sum và đoạn con

Mục tiêu:

• chuyển đoạn con thành hiệu hai Prefix Sum;
• đếm tổng bằng $x$;
• đếm tổng chia hết;
• biến đổi điều kiện về Prefix bằng nhau.

---

Tầng 4 — Prefix Sum và tối ưu

Mục tiêu:

• maximum subarray;
• đoạn có giới hạn độ dài;
• đoạn ngắn nhất đạt ngưỡng;
• Prefix Maximum;
• Binary Search;
• cấu trúc đơn điệu.

---

Tầng 5 — Prefix nhiều chiều

Mục tiêu:

• 2D Prefix Sum;
• Inclusion-Exclusion;
• Rectangle Query;
• Threshold Matrix;
• Coordinate Compression;
• 3D Prefix Sum.

---

Tầng 6 — Difference Array

Mục tiêu:

• Range Update;
• phủ đoạn;
• nhiều lớp cập nhật;
• 2D Difference;
• Imos Method.

---

Tầng 7 — Prefix nâng cao

Mục tiêu:

• Prefix cấp hai;
• tổng của nhiều subarray;
• Flatten subarray sums;
• Prefix kết hợp Fenwick Tree;
• chuyển từ Static Query sang Dynamic Query.

---

67. Mục tiêu sau khi hoàn thành serie

Sau khi hoàn thành toàn bộ serie, người học cần có khả năng nhận ra các biểu hiện sau:

• “nhiều truy vấn tổng đoạn” $\rightarrow$ Prefix Sum;
• “đếm điều kiện trên đoạn” $\rightarrow$ Prefix Count;
• “XOR đoạn” $\rightarrow$ Prefix XOR;
• “đếm đoạn có tổng $x$” $\rightarrow$ hai Prefix Sum;
• “chia hết cho $m$” $\rightarrow$ phần dư Prefix Sum;
• “maximum subarray” $\rightarrow$ Prefix Sum nhỏ nhất phía trước;
• “nhiều Rectangle Query” $\rightarrow$ 2D Prefix Sum;
• “nhiều Cuboid Query” $\rightarrow$ 3D Prefix Sum;
• “nhiều cập nhật đoạn” $\rightarrow$ Difference Array;
• “nhiều cập nhật hình chữ nhật” $\rightarrow$ 2D Difference;
• “truy vấn trên các phép cập nhật” $\rightarrow$ Difference nhiều tầng;
• “tổng của nhiều tổng đoạn” $\rightarrow$ Prefix của Prefix;
• “cập nhật động” $\rightarrow$ Fenwick Tree hoặc Segment Tree.

Quan trọng hơn, cần hình thành phản xạ:

Khi thấy một đoạn liên tiếp, hãy thử biểu diễn nó bằng hiệu của hai tiền tố.

---

68. Công thức tổng kết

Một chiều:

$$\boxed{ P_i=P_{i-1}+a_i }$$ $$\boxed{ S(l,r)=P_r-P_{l-1} }$$

Hai chiều:

$$\boxed{ P_{i,j} = a_{i,j} + P_{i-1,j} + P_{i,j-1} - P_{i-1,j-1} }$$

Ba chiều:

$$\boxed{ \begin{aligned} P_{x,y,z} ={}&a_{x,y,z} +P_{x-1,y,z} +P_{x,y-1,z} +P_{x,y,z-1}\\ &-P_{x-1,y-1,z} -P_{x-1,y,z-1} -P_{x,y-1,z-1}\\ &+P_{x-1,y-1,z-1} \end{aligned} }$$

Difference Array:

$$\boxed{ D_l\mathrel{+}=x }$$ $$\boxed{ D_{r+1}\mathrel{-}=x }$$

Đếm đoạn tổng $x$:

$$\boxed{ P_i=P_j-x }$$

Đếm đoạn chia hết cho $m$:

$$\boxed{ P_i\equiv P_j\pmod m }$$

Maximum Subarray:

$$\boxed{ \max_r \left( P_r-\min_{0\le i<r}P_i \right) }$$

Prefix cấp hai:

$$\boxed{ Q_i=\sum_{j=1}^{i}P_j }$$

Tổng mọi đoạn con:

$$\boxed{ \sum_{i=1}^{n}a_i\,i(n-i+1) }$$

Đây là hệ công thức cốt lõi của toàn bộ chuyên đề Prefix Sum.