Wiki › Cấu trúc dữ liệu › Mảng & Xâu ký tự

Mảng & Xâu ký tự

huunguyen Updated Tháng sáu 2, 2026

Mảng (array) và xâu ký tự (string) là hai cấu trúc dữ liệu nền tảng nhất trong lập trình thi đấu: gần như mọi bài toán đều bắt đầu từ việc đọc dữ liệu vào một mảng hoặc một xâu. Trang này tổng hợp cách dùng chúng trong C++/Python, và quan trọng nhất là hai kỹ thuật tăng tốc kinh điển — tổng tiền tố (prefix sum) và mảng hiệu (difference array) — giúp trả lời truy vấn tổng đoạn hoặc cập nhật đoạn trong $O (1)$ thay vì $O (N)$ mỗi lần, đưa nhiều bài từ $O (N Q)$ về $O (N + Q)$ .

Mảng (Array)

Mảng lưu trữ các phần tử cùng kiểu liên tiếp trong bộ nhớ. Nhờ liên tiếp, địa chỉ phần tử thứ $i$ tính được bằng một phép nhân–cộng, nên truy cập theo chỉ số là $O (1)$ .

C++

int a[100005];               // mảng tĩnh, đủ lớn, khai báo ngoài main để nằm vùng nhớ global

vector<int> v = {1, 2, 3};   // mảng động
v.push_back(6);              // thêm cuối: O(1) khấu trừ (amortized)
v.pop_back();                // xóa cuối: O(1)
v[i];                        // truy cập: O(1)
int n = v.size();

vector<vector<int>> mat(n, vector<int>(m, 0));   // ma trận n x m, khởi tạo 0

Python

a = [1, 2, 3]
a.append(6)
a.pop()
a[i]
mat = [[0] * m for _ in range(n)]   # KHÔNG dùng [[0]*m]*n (các hàng trỏ chung 1 list!)

Xâu ký tự (String)

C++

string s = "hello";
s.length();          // độ dài
s[i];                // ký tự thứ i (char)
s.substr(l, len);    // xâu con bắt đầu ở l, dài len
s.find("ell");       // vị trí xuất hiện đầu tiên, hoặc string::npos nếu không có
s += " world";
for (char c : s) { /* ... */ }

Python

s = "hello"
len(s); s[i]; s[l:r]
s.find("ell")
s.split()
",".join(lst)

Ý tưởng / Trực giác

Tổng tiền tố. Giả sử ta phải trả lời nhiều truy vấn "tổng các phần tử từ $l$ đến $r$ ". Tính trực tiếp mỗi truy vấn mất $O (N)$ , $Q$ truy vấn là $O (N Q)$ — quá chậm. Quan sát then chốt: nếu đặt $pre [i] = a_{0} + a_{1} + \dots + a_{i - 1}$ (tổng của $i$ phần tử đầu, với $pre [0] = 0$ ), thì tổng đoạn $[l, r]$ chính là $a_{l} + \dots + a_{r} = pre [r + 1] - pre [l] .$ Lý do: $pre [r + 1]$ gồm mọi phần tử tới chỉ số $r$ , còn $pre [l]$ gồm mọi phần tử trước $l$ ; trừ đi thì phần đầu triệt tiêu, đúng bằng đoạn cần. Mỗi truy vấn chỉ còn một phép trừ $O (1)$ . Đây là ý tưởng "tính trước phần dùng chung, sau đó tái sử dụng".

Mảng hiệu là bài toán đối ngẫu: thay vì truy vấn đoạn, ta cần cộng một giá trị $v$ vào toàn bộ đoạn $[l, r]$ nhiều lần, rồi cuối cùng mới đọc mảng. Thay vì sửa từng phần tử ( $O (N)$ mỗi lần), ta chỉ ghi nhận "tại $l$ bắt đầu tăng thêm $v$ , tại $r + 1$ thì hết tăng": $diff [l] + = v$ , $diff [r + 1] - = v$ . Sau khi xử lý hết, lấy tổng tiền tố của $diff$ sẽ ra mảng kết quả. Trực giác: tổng tiền tố và mảng hiệu là hai phép toán nghịch đảo của nhau (giống đạo hàm và tích phân rời rạc).

Ví dụ chạy tay (tổng tiền tố)

Mảng $a = [3, 1, 4, 1, 5]$ (0-indexed). Tính $pre$ :

 i :   0    1    2    3    4    5
a  :   3    1    4    1    5
pre:   0    3    4    8    9   14
       ^cộng dồn: pre[i+1] = pre[i] + a[i]

Truy vấn tổng đoạn $[1, 3]$ (tức $a_{1} + a_{2} + a_{3} = 1 + 4 + 1 = 6$ ):

pre[4] - pre[1] = 9 - 3 = 6   ✔
        └────────┘
   bỏ đi 3 phần tử trước l=1, giữ tới r=3

Ví dụ chạy tay (mảng hiệu)

Ban đầu $a = [0, 0, 0, 0, 0]$ . Thực hiện hai thao tác cộng đoạn: cộng $2$ vào $[1, 3]$ , rồi cộng $5$ vào $[0, 2]$ .

Bước 1: +2 vào [1,3]   ->  diff[1]+=2, diff[4]-=2
Bước 2: +5 vào [0,2]   ->  diff[0]+=5, diff[3]-=5

 idx :    0    1    2    3    4
 diff:    5    2    0   -5   -2
          ^op2 ^op1     ^op2 ^op1
                       (đóng)(đóng)

Lấy tổng tiền tố của diff để khôi phục a:
 a[0]=5
 a[1]=5+2=7
 a[2]=7+0=7
 a[3]=7-5=2
 a[4]=2-2=0
 => a = [5, 7, 7, 2, 0]   ✔ (đúng: [0,1,2] +5, [1,2,3] +2)

Cài đặt

Tổng tiền tố 1D (C++):

vector<long long> pre(n + 1, 0);              // long long: tổng có thể tràn int
for (int i = 0; i < n; i++)
    pre[i + 1] = pre[i] + a[i];               // pre[i+1] gồm i+1 phần tử đầu
// tổng đoạn [l, r] (0-indexed, gồm cả r):
long long sum = pre[r + 1] - pre[l];

Mảng hiệu 1D (C++):

vector<long long> diff(n + 1, 0);
// cộng v vào mọi phần tử trong [l, r]:
diff[l] += v;
if (r + 1 < (int)diff.size()) diff[r + 1] -= v;
// khôi phục mảng cuối cùng bằng tổng tiền tố:
vector<long long> a(n);
long long run = 0;
for (int i = 0; i < n; i++) { run += diff[i]; a[i] = run; }

Tổng tiền tố 2D (cho ma trận, dùng trong bài chụp ảnh $K \times K$ ):

// pre[i][j] = tổng vùng từ (0,0) tới (i-1,j-1)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        pre[i][j] = g[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
// tổng hình chữ nhật góc trên-trái (r1,c1), góc dưới-phải (r2,c2) (0-indexed):
long long s = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];

Python (tổng tiền tố 1D):

pre = [0] * (n + 1)
for i in range(n):
    pre[i + 1] = pre[i] + a[i]
total = pre[r + 1] - pre[l]

Độ phức tạp

Tổng tiền tố: dựng mảng $pre$ duyệt 1 lần $O (N)$ ; mỗi truy vấn đoạn $O (1)$ (một phép trừ). Tổng $Q$ truy vấn: $O (N + Q)$ thay cho $O (N Q)$ . Bộ nhớ $O (N)$ cho mảng phụ.
Tổng tiền tố 2D: dựng $O (N M)$ , mỗi truy vấn hình chữ nhật $O (1)$ (bốn phép cộng/trừ). Bộ nhớ $O (N M)$ .
Mảng hiệu: mỗi thao tác cộng đoạn $O (1)$ (sửa 2 ô); khôi phục cuối cùng $O (N)$ . Với $U$ thao tác: $O (N + U)$ . Bộ nhớ $O (N)$ .

Lý do $O (1)$ mỗi truy vấn: công thức chỉ đụng tới một số hằng ô của mảng phụ, không phụ thuộc độ dài đoạn.

⚠️ Lỗi thường gặp

Tràn số (overflow). Tổng của tới $10^{5}$ phần tử mỗi phần tử cỡ $10^{9}$ vượt xa giới hạn int ( $\approx 2.1 \times 10^{9}$ ). Luôn để mảng $pre$ kiểu long long trong C++; quên điều này cho kết quả âm/sai khó debug.
Lệch chỉ số (off-by-one). Quy ước $pre [i]$ = tổng $i$ phần tử đầu nên tổng $[l, r]$ là $pre [r + 1] - pre [l]$ , không phải $pre [r] - pre [l]$ . Nhầm sẽ thiếu hoặc thừa đúng một phần tử ở biên.
Sai biên mảng hiệu. Khi cộng đoạn $[l, r]$ phải trừ tại $r + 1$ ; nếu $r + 1$ bằng $n$ (ngoài mảng gốc) cần cấp mảng $diff$ kích thước $n + 1$ , nếu không sẽ ghi tràn (out-of-bounds) hoặc bỏ sót việc "đóng" đoạn.
Khởi tạo ma trận Python sai. [[0]*m]*n tạo $n$ tham chiếu tới cùng một list — sửa một hàng làm mọi hàng đổi theo. Dùng [[0]*m for _ in range(n)].
Nối xâu trong vòng lặp $O (N^{2})$ . Trong C++ s += c lặp lại nhiều lần với chuỗi dài, hay trong Python s = s + c (str là immutable), đều tốn $O (N^{2})$ . Dùng stringstream/vector<char> ở C++ và "".join(list) ở Python.
Quên modulo khi dùng tổng tiền tố để đếm theo số dư. Khi đếm dãy con có tổng chia hết cho $k$ , ta so sánh $pre$ theo số dư; nhớ lấy $((x mod k) + k) mod k$ để tránh số dư âm nếu mảng có giá trị âm.

Biến thể / Mở rộng

Tổng tiền tố trên số dư (đếm dãy con có tổng chia hết cho $k$ ): xem bài div7 ở dưới.
Tổng tiền tố 2D cho truy vấn tổng hình chữ nhật.
Khi cần truy vấn đoạn xen kẽ với cập nhật điểm, tổng tiền tố không còn đủ — chuyển sang Cây Fenwick hoặc Cây phân đoạn.

Bài tập luyện

Biên Độ Điểm Quidditch (quidrange) — (Sơ cấp) Đọc mảng và tìm max − min: làm quen thao tác duyệt mảng cơ bản.
Ký Tự Phổ Biến (charfreq) — (Học việc) Đếm tần suất ký tự bằng mảng đếm 26 phần tử trên một xâu.
Chụp Ảnh (photos26) — (Học việc) Tổng tiền tố 2D để lấy tổng mọi vùng $K \times K$ nhanh.
Đếm giống bò (bcount) — (Trung cấp) Dùng tổng tiền tố theo từng loại để trả lời truy vấn đếm trên đoạn trong $O (1)$ .
Dãy con chia hết cho 7 (div7) — (Trung cấp) Tổng tiền tố kết hợp số dư modulo để tìm dãy con dài nhất chia hết cho 7.
Toa xe Hogwarts Express (hogexpress) — (Trung cấp) Mảng hiệu: cộng $1$ vào nhiều đoạn $[l, r]$ rồi tìm vị trí có giá trị lớn nhất.