Mảng cộng dồn là việc tạo ra một mảng mới có kích thước bằng với mảng ban đầu+1 và phần tử thứ ~i~ của mảng mới được tạo ra bằng cách tính tổng i phần tử đầu tiên của mảng ban đầu. Ta có thể hiểu phần tử đầu tiên của mảng cộng dồn là 0 và phần tử cuối cùng của mảng cộng dồn là tổng tất cả các phần tử trong mảng ban đầu. Với việc tạo ra mảng cộng dồn ta có thể tính toán tổng các phần tử từ vị trí thứ ~x~ đến vị trí thứ ~y~ trên mảng ban đầu mà không cần phải tính toán lại từ đầu. Ví dụ cho mảng ~A~ gồm các phần tử lần lượt như sau A= {3,7,-6,5,9,11,3,21} Từ mảng A ban đầu ta có thể tạo ra mảng Prefix Sum của ~A~ như sau PreA = {3,10,4,9,18,29,32,53}. Để tính tổng các phần tử từ 3 đến 7 trong mảng ~A~ ta có thể thực hiện như sau T1=-6+5+9+11+3 = 22 hoặc sử dụng mảng cộng dồn để tính như sau T2= PreA₇ - PreA₂ = 32 - 10 = 22.

Chứng minh như sau : Ta có tổng các phần tử từ 1 đến 7 là PreA₇, tổng các phần tử từ 1 đến 2 là PreA₂. Vậy để tính tổng các phần tử từ 3 đến 7 ta lấy PreA₇-PreA₂.
Vậy với cách làm này ta áp dụng trong trường hợp nào. Giả sử cho một mảng có ~M~ phần tử cho ~N~ đoạn khác nhau (~x~_i,~y~_i) (~M~<=10⁸,~N~ ≤ 100), hỏi đoạn có tổng các phần tử là lớn nhất là bao nhiêu
Đối với bài tập này ta có thể sử dụng phương pháp cày trâu như sau sử dụng một vòng lặp for từ 1 đến ~N~, với mỗi ~i~ ta tính tổng các phần tử trong đoạn (~x~_i,~y~_i) bằng cách sử dụng vòng lặp for( độ phức tạp O(~y~ _i - ~x~ _i)). Với cách làm này độ phức tạp của thuật toán ~O(MxN), cách làm chỉ thực hiện được khi M ≤ 10₆, nếu lớn hơn sẽ quá thời gian.
Nếu sử dụng Prefix Sum ta tạo 1 mảng Pre (độ phức tạp ~O(N)~), Sử dụng một vòng lặp for từ 1 đến ~N~, với mỗi ~i~ ta tính tổng các phần tử trong đoạn (~x~_i,~y~_i) bằng cách sử dụng công thức Prefix Sum (độ phức tạp O(1)). Vậy độ phức tạp của thuật toán là O(N) sẽ thỏa mãn thời gian thực hiện
Mảng cộng dồn 2 chiều
Cho mảng 2 chiều A có 4x4 phần tử ta có thể xây dựng mảng 2 chiều là mảng cộng dồn của A có 5x5 phần tử trong đó cột 0 và dòng 0 nhận giá trị = 0. Phần tử tại vị trí có tọa độ (x,y) có giá trị bằng tổng tất cả các phần tử trong hình chữ nhật được giới hạn trong phạm vi từ(1,1) đến (x,y) Ví dụ để tính phần tử tại vị trí (2,1) của mảng cộng dồn ta tính như sau = 3 + (-6) = -3
Ví dụ để tính phần tử tại vị trí (3,2) của mảng cộng dồn ta tính như sau = 3 + (-6) + 7 + (-7) + 9 + 4 = 10
Với cách làm như trên ta thu được mảng cộng dồn của 1 mảng 2 chiều.
Với cách làm trên độ phức tạp khá lớn nên ta cải tiến cách làm như sau:
Bước 1: Set 0 cho dòng 0 và cột 0
Bước 2: Tính giá trị Pre[x,y] = Pre[x-1,y]+Pre[x,y-1]-Pre[x-1,y-1]
Ứng dụng
Để tính tổng phần tử từ (1,1) đến (x,y) ta lấy giá trị tại mảng Pre[x,y]
Để tính tổng phần tử từ (1,y₁) đến (x₂,y₂) ta lấy Pre[x₂,y₂]-Pre[x₂,y₁-1]
Để tính tổng phần tử từ (x₁,1) đến (x₂,y₂) ta lấy Pre[x₂,y₂]-Pre[x₂-1,y₂]
Để tính tổng phần tử từ (x₁,y₁) đến (x₂,y₂) ta lấy Pre[x₂,y₂] - Pre[x₁-1,y₂] - Pre[x₂,y₂-1] + Pre[x₁-1,y₁-1]
Chứng minh công thức Các em tự chứng minh nhé, kẻ bảng sẽ hiểu rõ hơn