---
# System prepended metadata

title: (78A) **Prefix - sum - mãng cộng dồn**

---

# (78A) **Prefix - sum - mãng cộng dồn**
## **Lý thuyết prefix sum 1 chiều**
Cho một mảng $A$ có $n$ phần tử được đánh số từ $1$ đến $n$. Ta xây dựng 1 mãng $S$ như sau:
- $S_0 = 0$
- $S_i = S_{i - 1} + a_i$

**Ví dụ:** Cho mảng $A$ có giá trị như sau:
![](https://i.imgur.com/X2FDAjW.jpg)

Xây dựng mãng S dựa trên công thức trên, ta có mãng $S$ có giá trị như sau:
![](https://i.imgur.com/9BUtvrc.jpg)
- $S_i$ là tổng các phần tử từ $1$ đến $i$ của mãng $A$ 

### Cài đặt
```cpp=
{
    for (int i = 1; i <= n; i++) cin >> a[i];
    s[0] = 0;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
}
```
### **Áp dụng**
Để tính tổng từ phần tử thứ $u$ đến phần tử thứ $v$ trong mãng $A$ ta làm như sau:
#### **Cày trâu**
```cpp=
int sum(int u, int v) {
    int s = 0;
    for (int i = u; i <= v; i++) s += a[i];
    return s;
}
```
- **ĐPT: O(n)**
#### **Áp dụng prefix - sum**
```cpp=
int sum(int u, int v) {
    return s[v] - s[u - 1];
}
```
- **ĐPT: O(1)**
- **Giải thích:**
    + Ta có $s_v$ là tổng các phần tử từ $1$ đến $v$ của mãng $A$. Tương tự với $s_{u - 1}$.
    + $s_v = a_1 + a_2 + a_3 + ... + a_{v - 2} + a_{v - 1} + a_{v}$
    + $s_{u - 1} = a_1 + a_2 + a_3 + ... + a_{u - 3} + a_{u - 2} + a_{u - 1}$
    + $s_v - s_{u - 1} =  (a_1 + a_2 + a_3 + ... + a_{v - 2} + a_{v - 1} + a_{v}) - (a_1 + a_2 + a_3 + ... + a_{u - 3} + a_{u - 2} + a_{u - 1})$ 
    + $=> s_v - s_{u - 1} = a_u + a_{u + 1} + ... + a_{v - 1} + a_{v}$ (hình dưới)
    ![](https://i.imgur.com/I5UNGIY.jpg)
    + Màu đỏ: $s_v$
    + Màu vàng: $s_{u - 1}$
    + Màu xanh: $s_v - s_{u - 1}$
## **Bài tập**
### sumseq
**Hint:** Mãng cộng dồn cơ bản
```cpp=
{
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    while (q--) {
        int u, v; cin >> u >> v;
        if (s[v] - s[u - 1] < x) ans++;
    }
    cout << ans << "\n";
}
```
### seq11
**Hint:** $(a - b)$ $mod$ $k$ $= 0$  $<=>$ $a$ $mod$ $k$ - $b$ $mod$ $k$ $= 0$ $<=>$ $a$ $mod$ $k$ $=$ $b$ $mod$ $k$
#### Cày trâu
```cpp=
{
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) if ((s[j] - s[i - 1]) % k == 0) {
            ans = max(ans, j - i + 1);
        }
    }
}
```
**ĐPT: O($n ^ 2$)**
- Tổng từ $u => v = s_v - s_{u -1}$
- $s_v - s_{u - 1}$ $mod$ $k = 0$ $=>$ $s_v$ $mod$ $k = s_{u - 1}$ $mod$ $k$ 
#### Thuận chuẩn
- Xét tới i có $S_i$ => Ta cần tìm j sao cho $S_j$ = $S_i$ để tổng từ vị trí j + 1 tới i chia hết cho x
- Để dài nhất thì cần tìm vị trí j xa i nhất thì độ dài mới dài nhất
- Dùng 1 mãng để lưu lại vị trí đầu tiên xuất hiện $S_j$
```cpp=
{
    for (int i = 1; i <= n; i++) 
        s[i] = (s[i - 1] + a[i]) % x;
    
    for (int i = 1; i <= n; i++) 
        if (vt[s[i]] == 0) vt[s[i]] = i;
    vt[0] = 0; 
    // bởi vì vị trí 0 xa nhất là s[0]
    /* nếu không gắn lại thì có thể vt[0] != 0 
     bởi vì s[i] bất kỳ có thể = 0 */
    
    for (int i = 1; i <= n; i++) {
        // vị trí i có tổng là s[i];
        ans = max(ans, i - vt[s[i]]);
    }
}
```

### seq12
**Hint:** Prefix sum + Chặt nhị phân
#### Cày trâu
- Duyệt qua hết tất cả các khoảng thời gian, trong đó $i$ là thời gian bắt đầu, $j$ là khoảng thời gian kết thúc.
- Tính tổng lợi nhuận trong thời gian $i$ và $j$ là  $sum_j - sum_{i - 1}$;

```cpp=
{
    // mãng cộng dồn sum;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (sum[j] - sum[i - 1] >= v) {
                ans += (n - j + 1);
                break;
            }
        }   
    }
    cout << ans << "\n";
}
```
#### Thuật AC
- Nhận thấy với 1 thời gian bắt bất kỳ, cần tìm vị trị đầu tiên vượt qua chỉ tiêu $v$. Từ đó tất cả vị trí sau đều quá chỉ tiêu $v$
- xét thời gian kết thúc là $mid$, 
    + Nếu $sum_mid - s_{i - 1} >= v$ thì: $r = mid - 1$
    + Ngược lại, $l = mid + 1$
    + Đáp án sẽ là $ans += (n - x + 1)$ với $x$ là vị trí đầu tiên thỏa mãn quá chỉ tiêu;
```cpp=
for (i)
{
    int l = i, r = n, mid, x = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (sum[mid] - sum[i - 1] >= v) {
            x = mid;
            r = mid - 1;
        } else l = mid + 1; 
    }
    if (x != -1) ans += ...;
}
```
### Bài 5 - CSES - Maximum Subarray Sum
#### Solution:
- Mình cần tìm $s_j$ - $s_{i - 1}$ lớn nhất
- Giả sử ta có $s_j$ và để $s_j$ - $s_{i - 1}$ lớn nhất thì $s_{i - 1}$ nhỏ nhất.
- Cách làm: Ta duyệt for là $s_j$, với mỗi $s_j$ ta kiểm tra kết quả với $s_j - m$ với m là min($s_i$) với $i$ từ $1 -> j - 1$
```cpp=
{
    int m = 0; // s[0] = 0;
    for (int j = 1; j <= n; j++) {
        kq = max(kq, s[j] - m);
        m = min(m, s[j]);
    }
    in ra kq;
}
```
### Bài 4 - Bài dễ (DHBB)
#### Solution:
- Là bài 5, nhưng thêm sàng nguyên tố
#### Code
```cpp=
{
    sangNT();
    ll m = 1e18;
    for (int i = 2; i <= n; i++) 
        if (i là số ngt) {
            kq = max(kq, s[i] - m);
            m = min(m, s[i - 1]);
        }
    for (int i = 2; i <= n; i++)
        if (i là số ngto) 
            kq = max(kq, a[i]);
}
```
### Bài 7 - Tích đặc biệt
#### Solution: 
- Tính tổng của các tích $a_i * a_j$ trong đó với mọi $j > i$.
- Ta có thể viết công thức dưới dạng: $(a_i * a_j) + (a_i * a_{j + 1}) + (a_i * a_{j + 2 }) + ... + (a_i * a_n)$
- Rút $a_i$ ra làm thừa số chung, ta có: $a_i * (a_j + a_{j + 1} + a_{j + 2} + ... + a_n)$
- for với mỗi vị trí $i$, mình tính tích của $a_i$ với tổng các các số từ $j + 1 -> n$ bằng prefix sum array
```cpp=
{
    for i:
        ans += a[i] * (s[n] - s[i]);
    
}
```

a
a
a
a
a
a
a
a
a
a
a
a
a
a
