# (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:
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:
- $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)
+ 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
Google Drive
Gist
Clipboard
Sign in with Wallet
