Bài 13: Mảng đánh dấu, đếm phân phối và mảng cộng dồn (prefix sum), mảng hiệu trong C++ và Python
Lời mở đầu
Bạn hãy thử đề này: “Cho dãy $n = 10^5$ số và $q = 10^5$ câu hỏi, mỗi câu hỏi tổng các số từ vị trí $l$ tới $r$ là bao nhiêu?”. Cách tự nhiên là với mỗi câu hỏi chạy một vòng lặp cộng từ $l$ tới $r$, tệ nhất $q \cdot n = 10^{10}$ phép tính → TLE chắc chắn (xem bài 9). Với kỹ thuật mảng cộng dồn của bài này, ta chuẩn bị trước mất $O(n)$, sau đó trả lời mỗi câu hỏi chỉ bằng một phép trừ. Tương tự, mảng đánh dấu và đếm phân phối giúp trả lời “số $x$ có xuất hiện không, xuất hiện mấy lần?” trong $O(1)$ thay vì phải dò cả mảng. Đây là các kỹ thuật “rẻ mà mạnh” đầu tiên em nên thuộc lòng.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Mảng đánh dấu: số này đã xuất hiện chưa?
Ý tưởng: dùng chính giá trị làm chỉ số. Tạo mảng bool da[MAX] toàn false; mỗi khi đọc được số $x$ thì gán da[x] = true. Sau đó muốn biết $x$ có xuất hiện không, chỉ cần nhìn da[x]: $O(1)$, thay vì dò cả dãy $O(n)$. Điều kiện để dùng được: các giá trị là số nguyên không âm và không quá lớn (cỡ $10^6$ – $10^7$, vì cần một mảng kích thước bằng giá trị lớn nhất). Nếu giá trị lớn tới $10^9$ thì dùng set hoặc map ở bài 11.
Ví dụ: tìm MEX, tức số nguyên dương nhỏ nhất không xuất hiện trong dãy. Đánh dấu mọi số, rồi đi từ 1 lên, gặp ô false đầu tiên là đáp án. Vì dãy có $n$ số nên đáp án không vượt quá $n + 1$, các số lớn hơn $n$ có thể bỏ qua luôn, nhờ vậy mảng chỉ cần kích thước $n + 2$ dù giá trị lớn cỡ nào.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
bool da[1000005];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int x; cin >> x;
if(x >= 1 && x <= n) da[x] = true;
}
int mex = 1;
while(da[mex]) mex++;
cout << mex;
return 0;
}n = int(input())
a = list(map(int, input().split()))
da = [False] * (n + 2)
for x in a:
if 1 <= x <= n:
da[x] = True
mex = 1
while da[mex]:
mex += 1
print(mex)Phần 2Đếm phân phối: số này xuất hiện mấy lần?
Nâng cấp mảng đánh dấu: thay bool bằng int và thay vì gán true thì tăng thêm 1: dem[x]++. Khi đó dem[x] cho biết số $x$ xuất hiện bao nhiêu lần. Một ứng dụng đẹp là sắp xếp đếm phân phối (counting sort): đếm xong, chỉ cần đi từ giá trị nhỏ tới lớn và in mỗi giá trị $v$ đúng dem[v] lần là được dãy tăng dần! Độ phức tạp $O(n + V)$ với $V$ là giá trị lớn nhất, nhanh hơn cả sort $O(n \log n)$ khi $V$ nhỏ.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int dem[1000005];
int main(){
int n;
cin >> n;
int mx = 0;
for(int i = 0; i < n; i++){
int x; cin >> x;
dem[x]++;
mx = max(mx, x);
}
for(int v = 0; v <= mx; v++)
for(int k = 0; k < dem[v]; k++)
cout << v << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
mx = max(a)
dem = [0] * (mx + 1)
for x in a:
dem[x] += 1
kq = []
for v in range(mx + 1):
kq.extend([v] * dem[v])
print(*kq)dem[x + 1000000]. Giá trị quá lớn ($10^9$, $10^{18}$): mảng không đủ bộ nhớ, dùng map hoặc sắp xếp rồi đếm các đoạn bằng nhau. Giá trị không phải số nguyên (số thực, xâu): dùng map. Với chữ cái, mảng dem[26] và chỉ số c - 'a' (xem bài 8) là lựa chọn kinh điển.Mô phỏng trực quan. Đọc code đếm phân phối xong nhiều bạn vẫn thắc mắc: "không so sánh gì mà sao dãy lại tăng dần được?". Em bấm Tiếp từng bước để thấy mỗi số được "thả" thẳng vào ô có chỉ số bằng chính nó, rồi đọc lại mảng cnt từ trái sang phải nhé.
Phần 3Mảng cộng dồn: tổng một đoạn trong O(1)
Cho dãy $a_1, a_2, \dots, a_n$ (đánh số từ 1 cho tiện). Định nghĩa mảng cộng dồn (prefix sum) $S_i = a_1 + a_2 + \dots + a_i$ là tổng $i$ phần tử đầu, với $S_0 = 0$. Ta tính được toàn bộ $S$ trong $O(n)$ nhờ công thức $S_i = S_{i-1} + a_i$. Khi đó tổng đoạn từ $l$ tới $r$ bằng “tổng $r$ phần tử đầu” trừ đi “tổng $l - 1$ phần tử đầu”:
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
long long a[100005], S[100005];
int main(){
int n, q;
cin >> n >> q;
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];
while(q--){
int l, r; cin >> l >> r;
cout << S[r] - S[l - 1] << "\n";
}
return 0;
}import sys
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:2 + n]))
S = [0] * (n + 1)
for i in range(1, n + 1):
S[i] = S[i - 1] + a[i]
out, p = [], 2 + n
for _ in range(q):
l, r = int(data[p]), int(data[p + 1]); p += 2
out.append(S[r] - S[l - 1])
print('\n'.join(map(str, out)))Thử với dữ liệu của em: nhập dãy và các câu hỏi $(l, r)$, mô phỏng sẽ xây mảng $S$ từng ô rồi cho thấy mỗi câu hỏi chỉ “nhìn” đúng hai ô $S[r]$ và $S[l-1]$. Bộ đếm bên dưới so sánh số phép cộng của cách cộng trực tiếp với cách dùng mảng cộng dồn.
Phần 4Mảng hiệu: cộng một giá trị vào cả đoạn trong O(1)
Bài toán ngược lại: có $q$ thao tác, mỗi thao tác cộng $v$ vào mọi phần tử từ $l$ tới $r$; cuối cùng in cả dãy. Cộng trực tiếp tốn $O(n)$ mỗi thao tác. Mẹo mảng hiệu $D$: mỗi thao tác chỉ làm hai việc D[l] += v và D[r + 1] -= v. Sau tất cả thao tác, lấy cộng dồn của $D$ sẽ được đúng lượng đã cộng vào từng vị trí: giá trị $v$ “bật lên” từ vị trí $l$ và bị “tắt đi” từ vị trí $r + 1$. Tổng độ phức tạp $O(n + q)$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
long long D[100005];
int main(){
int n, q;
cin >> n >> q;
while(q--){
int l, r; long long v;
cin >> l >> r >> v;
D[l] += v;
D[r + 1] -= v;
}
long long cur = 0;
for(int i = 1; i <= n; i++){
cur += D[i];
cout << cur << " ";
}
return 0;
}n, q = map(int, input().split())
D = [0] * (n + 2)
for _ in range(q):
l, r, v = map(int, input().split())
D[l] += v
D[r + 1] -= v
cur, kq = 0, []
for i in range(1, n + 1):
cur += D[i]
kq.append(cur)
print(*kq)Mô phỏng trực quan. Mảng hiệu là phần khó hình dung nhất của bài: chỉ sửa 2 ô mà cả đoạn lại được cộng thêm v. Em xem mỗi truy vấn chỉ chạm vào ô xanh và ô đỏ, rồi đến cuối mới cộng dồn một lần để "hiện hình" mảng a mới. Thử đổi mảng và truy vấn của riêng em nhé.
Bài tậpLuyện đánh dấu, đếm và cộng dồn
Giới hạn chung: $n, q \le 10^5$ (bài 4: $n \le 10^6$), giá trị $0 \le a_i \le 10^6$ trừ khi đề nói khác. Hãy để ý: cách làm “thẳng” nào cũng $O(n \cdot q)$ hoặc $O(n^2)$, đều TLE.
Cho dãy $n$ số và $q$ câu hỏi, mỗi câu hỏi một số $x$: in YES nếu $x$ có trong dãy, ngược lại NO.
5
3 8 1 8 6
3
8 2 6YES
NO
YES💡 Gợi ý
bool da[1000005], đánh dấu khi đọc dãy, mỗi câu hỏi in theo da[x]. Tổng $O(n + q)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool da[1000005];
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++){ int x; cin >> x; da[x] = true; }
int q; cin >> q;
while(q--){ int x; cin >> x; cout << (da[x] ? "YES" : "NO") << "\n"; }
return 0;
}n = int(input())
da = set(map(int, input().split()))
q = int(input())
print('\n'.join("YES" if int(x) in da else "NO" for x in input().split()))Cho dãy $n$ số nguyên (có thể âm, có thể lớn tới $10^9$). Tìm số nguyên dương nhỏ nhất không có trong dãy.
6
3 4 1 5 2 76💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool da[100005];
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++){ long long x; cin >> x; if(x >= 1 && x <= n) da[x] = true; }
int m = 1;
while(da[m]) m++;
cout << m;
return 0;
}n = int(input())
s = set(map(int, input().split()))
m = 1
while m in s:
m += 1
print(m)In theo thứ tự tăng dần các giá trị xuất hiện đúng một lần trong dãy.
7
4 2 4 9 2 3 11 3 9💡 Gợi ý
dem[x]++, rồi duyệt $v$ từ 0 tới giá trị lớn nhất, in những $v$ có dem[v] == 1.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int dem[1000005];
int main(){
int n; cin >> n;
int mx = 0;
for(int i = 0; i < n; i++){ int x; cin >> x; dem[x]++; mx = max(mx, x); }
for(int v = 0; v <= mx; v++) if(dem[v] == 1) cout << v << " ";
return 0;
}from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
print(*sorted(v for v in c if c[v] == 1))Cho $n \le 10^6$ số nguyên trong đoạn $[0, 10^6]$. In dãy đã sắp xếp tăng dần.
8
5 3 0 3 9 1 5 30 1 3 3 3 5 5 9💡 Gợi ý
sort.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int dem[1000005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
int mx = 0;
for(int i = 0; i < n; i++){ int x; cin >> x; dem[x]++; mx = max(mx, x); }
for(int v = 0; v <= mx; v++)
for(int k = 0; k < dem[v]; k++) cout << v << ' ';
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0]); a = list(map(int, data[1:1 + n]))
mx = max(a)
dem = [0] * (mx + 1)
for x in a:
dem[x] += 1
out = []
for v in range(mx + 1):
if dem[v]:
out.extend([str(v)] * dem[v])
print(' '.join(out))Cho dãy $n$ số nguyên ($|a_i| \le 10^9$) và $q$ câu hỏi $(l, r)$. Với mỗi câu hỏi in $a_l + \dots + a_r$.
5 3
1 2 3 4 5
1 3
2 5
4 46
14
4💡 Gợi ý
long long vì tổng có thể tới $10^{14}$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[100005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q; cin >> n >> q;
for(int i = 1; i <= n; i++){ long long x; cin >> x; S[i] = S[i - 1] + x; }
while(q--){ int l, r; cin >> l >> r; cout << S[r] - S[l - 1] << "\n"; }
return 0;
}import sys
d = sys.stdin.read().split()
n, q = int(d[0]), int(d[1])
S = [0] * (n + 1)
for i in range(1, n + 1):
S[i] = S[i - 1] + int(d[1 + i])
p, out = 2 + n, []
for _ in range(q):
l, r = int(d[p]), int(d[p + 1]); p += 2
out.append(S[r] - S[l - 1])
print('\n'.join(map(str, out)))Cho dãy $n$ số nguyên và $k$ ($1 \le k \le n$). Tìm tổng lớn nhất của $k$ phần tử liên tiếp.
7 3
2 -1 3 5 -2 4 17💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long S[100005];
int main(){
int n, k; cin >> n >> k;
for(int i = 1; i <= n; i++){ long long x; cin >> x; S[i] = S[i - 1] + x; }
long long best = LLONG_MIN;
for(int i = k; i <= n; i++) best = max(best, S[i] - S[i - k]);
cout << best;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
S = [0]
for x in a:
S.append(S[-1] + x)
print(max(S[i] - S[i - k] for i in range(k, n + 1)))Cho dãy $n$ số nguyên dương và $k$ ($k \le 10^6$). Đếm số đoạn con liên tiếp $[l, r]$ có tổng chia hết cho $k$.
5 3
1 2 3 4 57💡 Gợi ý
dem[S_i % k] với mọi $i$ từ 0 tới $n$ (đừng quên $S_0 = 0$); mỗi nhóm $c$ chỉ số cùng số dư tạo ra $\frac{c(c-1)}{2}$ đoạn. Kết hợp cả cộng dồn lẫn đếm phân phối, $O(n + k)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long dem[1000005];
int main(){
int n, k; cin >> n >> k;
long long s = 0, kq = 0;
dem[0] = 1; // S_0 = 0
for(int i = 1; i <= n; i++){
long long x; cin >> x;
s = (s + x) % k;
kq += dem[s]; // ghép với mọi chỉ số trước đó cùng số dư
dem[s]++;
}
cout << kq;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
dem = [0] * k
dem[0] = 1
s = kq = 0
for x in a:
s = (s + x) % k
kq += dem[s]
dem[s] += 1
print(kq)Có $n$ cây cao 0. Có $q$ lần tưới, lần thứ $j$ làm các cây từ $l_j$ tới $r_j$ cao thêm $v_j$. In chiều cao cuối cùng của từng cây.
5 3
1 3 2
2 5 1
4 4 52 3 3 6 1💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long D[100005];
int main(){
int n, q; cin >> n >> q;
while(q--){ int l, r; long long v; cin >> l >> r >> v; D[l] += v; D[r + 1] -= v; }
long long cur = 0;
for(int i = 1; i <= n; i++){ cur += D[i]; cout << cur << " "; }
return 0;
}n, q = map(int, input().split())
D = [0] * (n + 2)
for _ in range(q):
l, r, v = map(int, input().split())
D[l] += v; D[r + 1] -= v
cur, kq = 0, []
for i in range(1, n + 1):
cur += D[i]; kq.append(cur)
print(*kq)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét