# Mảng cộng dồn (Prefix Sum)
## Bài toán tính tổng
Cho dãy số $a_1, a_2, ..., a_n$. Có $q$ truy vấn mỗi truy vấn $[l_i, r_i]$ yêu cầu tính tổng các phần tử từ $a_{l_i}$ đến $a_{r_i}$ $(1 \le i \le q)$.

**Input**

7 3
2 -1 7 4 2 6 1
1 4
5 7
2 6

**Output**

12
9
18

### Thuật toán "ngây thơ"
Ta chỉ cần duyệt từ $[l_i,r_i]$ với mỗi truy vấn.

for (int i=1;i<=q;i++){
    cin>>l[i]>>r[i];  // nhap vao truy van thu i [l_i, r_i]
    for (int j=l[i];j<=r[i];j++){
        sum[i]+=a[j]; // tinh tong trong doan [l_i, r_i]
    }
}

Có $q$ truy vấn, mỗi truy vấn sẽ duyệt qua đoạn $[l_i,r_i]$ (duyệt qua tối đa $n$ phần tử) nên độ phức tạp thời gian là $O(q\cdot n)$.

$\rightarrow$ **Thuật toán không tối ưu**.
### Tối ưu chương trình
Có thể dùng Bảng thưa (Sparse Table), Cây phân đoạn (Segment Tree), Cây Fenwick (Fenwick Tree), Giải thuật Mo (Mo Algorithm), ... nhưng tối ưu nhất vẫn là **Mảng cộng dồn (Prefix Sum)**.
#### Khái niệm
Ta có mảng $A$ (Coi $A_0 = 0$) được cho trước, xây dựng mảng $S(A)$ theo quy tắc sau:
- $S_0 = 0$
- $S_i = \displaystyle \sum_{j = 0}^{i} A_j$ $=$ $S_{i - 1} + A_{i} = \displaystyle \sum_{j = 0}^{i - 1} A_j + A_i$, với $1 \le i \le n$

*Ví dụ:*
Ta có mảng $A$ $= \{2, -1, 7 ,4, 2, 6, 1\}$.
Xây dựng được mảng $S$ = $\{0, 2,1,8,12,14,20,21\}$.

#### Cài đặt mảng cộng dồn

s[0]=0;
for (int i=1;i<=n;i++){
    s[i]=s[i-1]+a[i]; // Xay dung mang S theo he thuc truy hoi
}

#### Tối ưu bài toán nêu trên
Để tối ưu được bài toán nêu trên, trước tiên ta cần giải bài toán nhỏ sau:
Chứng minh $\displaystyle \sum_{i=l}^{r} A_i = S_r - S_{l-1}$
*Bài giải*:
$$
\begin{align*}
S_r - S_{l-1} &= \displaystyle \sum_{i=0}^{r} A_i - \sum_{i=0}^{l-1} A_i \\
&= \displaystyle \sum_{i=0}^{l-1} A_i + \sum_{i=l}^{r} A_i - \sum_{i=0}^{l-1} A_i \\
&= \displaystyle \sum_{i=l}^{r} A_i
\end{align*}
$$
Vậy bài toán tính tổng có thể được giải bằng các bước sau:
- Tạo mảng cộng dồn S từ mảng A cho trước
- Với mỗi truy vấn $[l_i,r_i]$, kết quả sẽ là $S_{r_i} - S_{l_i-1}$.
#### Cài đặt

s[0]=0;
for (int i=1;i<=n;i++){
    s[i]=s[i-1]+a[i]; // Xay dung mang S theo he thuc truy hoi
}
for (int i=1;i<=q;i++){
    cin>>l[i]>>r[i];
    sum[i]=s[r[i]]-s[l[i]-1]; // Ket qua la S_ri - S_li-1
}

Xây dựng mảng cộng dồn mất $n$ thao tác, trả lời $q$ truy vấn, mỗi truy vấn $1$ thao tác nên độ phức tạp thời gian sẽ là $O(max(q,n))$.

$\rightarrow$ **Nhanh hơn rất nhiều so với cách làm "ngây thơ" không tối ưu**.
## Áp dụng trong bài toán dãy con có tổng lớn nhất
Cho một mảng $A$ gồm $n$ phần tử. Tìm đoạn con khác rỗng có tổng lớn nhất. Giới hạn: $1 \le n \le 2 \cdot 10^5$, $\lvert A_i \rvert \le 10^9$
**Input**

8
-1 3 -2 5 3 -5 2 2

**Output**

9

Đoạn con $\{3,-2,5,3\}$ có tổng lớn nhất.

*Bài giải:*

Trước hết, ta tạo mảng $pref = S(A)$ để lưu mảng cộng dồn của $A$. Giả sử với $r$ cố định, ta cần tìm $l < r$ sao cho tổng các phần tử trong nửa khoảng $[l, r)$ đạt cực đại. Ta viết lại bài toán theo công thức sau:

$$
\begin{align*}
ans_r &= \max_{0 \, \le \, l \, < \, r} (pref_r - pref_l) \\
&= pref_r + \max_{0 \, \le \, l \, < \, r} (- pref_l) \\
&= pref_r - \min_{0 \, \le \, l \, < \, r} pref_l \\
\end{align*}
$$

Nếu ta chạy $r$ từ $1$ đến $n$, ta có thể cập nhật cuốn chiếu $\min$ theo từng $pref_r$; việc này cho phép chúng ta tính $ans_r$ với độ phức tạp $O(1)$. Đáp án của bài toán là $\displaystyle \max_{r} ans_r$ với $1 \le r \le n$.

Độ phức tạp của cách trên là $\mathcal{O}(n)$.

// prefSum[i] la mang con don tai vi tri i
// prefMin[i] la gia tri nho nhat cua prefSum[0 ... i-1] 
prefSum[0] = prefMin[0] = 0; 
    for (int i = 1; i <= n; i++)
      prefSum[i] = prefSum[i - 1] + a[i];
      prefMin[i] = min(prefMin[i - 1], prefSum[i]);
    for (int i = 1; i <= n; i++)
        ans = max(ans, prefSum[i] - prefMin[i]);