Tổng tiền tố và mảng hiệu

Mức độ: Cơ bản

Đề cho dãy 10⁵ số và 10⁵ câu hỏi “tổng từ vị trí l đến r là bao nhiêu?”. Mỗi câu hỏi cộng lại từ đầu thì tổng cộng tới 10¹⁰ phép tính, quá chậm. Tổng tiền tố chuẩn bị trước một lần, sau đó mỗi câu hỏi chỉ cần một phép trừ. Đây là kỹ thuật xuất hiện trong rất nhiều đề học sinh giỏi.

Tổng tiền tố

Với dãy a₁, a₂, …, a_n, đặt P₀ = 0 và P_i = a₁ + a₂ + … + a_i (tổng i số đầu). Tính dần: P_i = P_{i - 1} + a_i.

i	0	1	2	3	4	5
ai		3	1	4	1	5
Pi	0	3	4	8	9	14

Tổng đoạn từ l đến r là tổng r số đầu bỏ đi tổng l - 1 số đầu:

tổng(l, r) = P_r - P_{l - 1}

Tổng từ 2 đến 4: P₄ - P₁ = 9 - 3 = 6 (đúng là 1 + 4 + 1).

Python

import sys
du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))
P = [0] * (n + 1)
for i in range(1, n + 1):
    P[i] = P[i - 1] + a[i - 1]
kq = []
vi_tri = 2 + n
for _ in range(q):
    l, r = int(du_lieu[vi_tri]), int(du_lieu[vi_tri + 1])
    vi_tri += 2
    kq.append(P[r] - P[l - 1])
print("\n".join(map(str, kq)))

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        P[i] = P[i - 1] + x;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";
    }
    return 0;
}

Lưu ý: dùng P₀ = 0 và đánh số từ 1 giúp công thức P_r - P_{l - 1} đúng cả khi l = 1, không cần xử lý riêng.

Ý tưởng tổng tiền tố đã xuất hiện ở nhiều bài trước: đếm bội số trong đoạn, đếm số nguyên tố trong đoạn, đoạn có tổng chia hết cho k.

Tổng tiền tố hai chiều

Với bảng m hàng, n cột, đặt S[i][j] = tổng hình chữ nhật từ góc trên trái (1, 1) đến ô (i, j). Tính bằng bù trừ:

S[i][j] = a[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1]

(phần S[i - 1][j - 1] bị cộng hai lần nên trừ đi một lần). Tổng hình chữ nhật từ (r₁, c₁) đến (r₂, c₂):

S[r₂][c₂] - S[r₁ - 1][c₂] - S[r₂][c₁ - 1] + S[r₁ - 1][c₁ - 1]

Lấy hình lớn, bỏ dải phía trên và dải bên trái, rồi cộng lại góc trên trái vì bị bỏ hai lần. Đây chính là nguyên lý bù trừ.

Mảng hiệu: cộng cả đoạn chỉ với hai phép tính

Bài toán ngược: có q lần “cộng v vào mọi phần tử từ l đến r”, cuối cùng in ra dãy. Cộng từng phần tử thì mỗi lần tốn tới n bước.

Dùng mảng hiệu D, với ý nghĩa: a_i = D₁ + D₂ + … + D_i (dãy a là tổng tiền tố của D). Cộng v vào đoạn [l, r] chỉ cần:

• D_l += v: từ vị trí l trở đi đều được cộng v.
• D_{r + 1} -= v: từ vị trí r + 1 trở đi trừ lại v, nên chỉ đoạn [l, r] bị ảnh hưởng.

Làm hết q lần, cuối cùng tính tổng tiền tố của D là được dãy kết quả.

Thao tác	D1	D2	D3	D4	D5	D6
ban đầu	0	0	0	0	0	0
cộng 5 vào [2, 4]	0	5	0	0	-5	0
cộng 2 vào [1, 3]	2	5	0	-2	-5	0
tổng tiền tố → a	2	7	7	5	0

Tổng tiền tố và mảng hiệu là hai phép ngược nhau: tính hiệu liền kề của P thì được a, tính tổng tiền tố của D thì được a.

Luyện tập

Gồm 22 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Tổng tiền tố một chiều

Bài 1. Tổng đoạn

Dòng đầu có n, q (n, q ≤ 10⁵). Dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Mỗi dòng trong q dòng tiếp theo có l, r (1 ≤ l ≤ r ≤ n). Với mỗi dòng, in ra tổng a_l + … + a_r.

Ví dụ:

Nhập	In ra
5 2 3 1 4 1 5 2 4 1 5	6 14

Kiểm tra: nhập

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

Xem đáp số

19
4
-2
10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đoạn độ dài k có tổng lớn nhất

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵). Dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra tổng lớn nhất của một đoạn gồm đúng k số liên tiếp.

Ví dụ:

Nhập	In ra
5 2 3 1 4 1 5	6

Kiểm tra: nhập

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

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Đếm đoạn có tổng bằng S

Dòng đầu có n, S (n ≤ 10⁵, |S| ≤ 10¹⁴). Dòng thứ hai có n số nguyên (có thể âm, |a_i| ≤ 10⁹). Đếm số đoạn liên tiếp (ít nhất một số) có tổng đúng bằng S.

Ví dụ:

Nhập	In ra
5 5 2 3 -1 4 2	2

Kiểm tra: nhập

8 0
1 -1 2 -2 3 -3 0 1

Xem đáp số

11

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Vị trí cân bằng

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên. Tìm vị trí i nhỏ nhất (đánh số từ 1) sao cho tổng các số bên trái i bằng tổng các số bên phải i (không tính a_i; bên trái vị trí 1 có tổng 0). Nếu không có in ra -1.

Ví dụ:

Nhập	In ra
5 1 2 3 2 1	3

Kiểm tra: nhập

7
-7 1 5 2 -4 3 0

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Đoạn con tổng lớn nhất

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra tổng lớn nhất của một đoạn liên tiếp gồm ít nhất một số.

Ví dụ:

Nhập	In ra
5 -2 3 -1 4 -5	6

Kiểm tra: nhập

9
-2 1 -3 4 -1 2 1 -5 4

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đoạn dài nhất có tổng bằng 0

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên. In ra độ dài đoạn liên tiếp dài nhất có tổng bằng 0 (in 0 nếu không có).

Ví dụ:

Nhập	In ra
5 1 2 -3 3 1	3

Kiểm tra: nhập

10
4 -2 -2 5 1 -6 3 -3 2 1

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Đếm số 0 trong đoạn

Dòng đầu có n, q (n, q ≤ 10⁵). Dòng thứ hai có n số nguyên. Mỗi dòng trong q dòng tiếp theo có l, r. Với mỗi câu hỏi in ra số lượng số 0 trong đoạn từ l đến r.

Ví dụ:

Nhập	In ra
6 2 0 1 0 0 5 0 1 3 2 5	2 2

Kiểm tra: nhập

10 3
3 0 0 7 0 1 0 0 0 2
1 10
4 6
7 9

Xem đáp số

6
1
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tổng tiền tố hai chiều

Bài 8. Tổng hình chữ nhật con

Dòng đầu có m, n, q (m, n ≤ 1000, q ≤ 10⁵). m dòng tiếp theo mỗi dòng n số nguyên. q dòng cuối mỗi dòng có r1, c1, r2, c2. Với mỗi câu hỏi in ra tổng các số trong hình chữ nhật từ ô (r1, c1) đến ô (r2, c2).

Ví dụ:

Nhập	In ra
2 3 2 1 2 3 4 5 6 1 1 2 2 2 2 2 3	12 11

Kiểm tra: nhập

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

Xem đáp số

21
7
-1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hình vuông k × k có tổng lớn nhất

Dòng đầu có m, n, k (k ≤ m, n ≤ 1000). m dòng tiếp theo mỗi dòng n số nguyên. In ra tổng lớn nhất của một hình vuông con k × k.

Ví dụ:

Nhập	In ra
3 3 2 1 2 3 4 5 6 7 8 9	28

Kiểm tra: nhập

4 5 2
1 -1 2 0 3
-2 4 1 5 -3
3 0 -4 2 6
1 2 3 -1 0

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Hình vuông không chứa ô cấm

Dòng đầu có m, n, k (k ≤ m, n ≤ 1000). m dòng tiếp theo là bản đồ gồm . (ô trống) và # (ô cấm). Đếm số hình vuông k × k chỉ gồm ô trống.

Ví dụ:

Nhập	In ra
3 3 2 ... .#. ...	0

Kiểm tra: nhập

4 5 2
..#..
.....
#....
...#.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Hình chữ nhật chứa đúng k ô đen

Dòng đầu có m, n, k (m, n ≤ 30). m dòng tiếp theo gồm các ký tự 0 (ô trắng) và 1 (ô đen). Đếm số hình chữ nhật con (cạnh song song với lưới) chứa đúng k ô đen.

Ví dụ:

Nhập	In ra
2 2 1 10 00	4

Kiểm tra: nhập

3 4 2
1001
0110
1000

Xem đáp số

14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Mảng hiệu

Bài 12. Cộng vào nhiều đoạn

Dòng đầu có n, q (n, q ≤ 10⁵). Dãy ban đầu gồm n số 0. Mỗi dòng trong q dòng tiếp theo có l, r, v: cộng v vào mọi phần tử từ l đến r. In ra dãy cuối cùng.

Ví dụ:

Nhập	In ra
5 2 2 4 5 1 3 2	2 7 7 5 0

Kiểm tra: nhập

8 4
1 8 1
3 5 10
5 8 -4
2 2 7

Xem đáp số

1 8 11 11 7 -3 -3 -3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Bật tắt đèn theo đoạn

Có n bóng đèn ban đầu đều tắt (n, q ≤ 10⁵). Có q lần thao tác, mỗi lần đảo trạng thái (tắt thành sáng, sáng thành tắt) mọi bóng từ l đến r. In ra số bóng đang sáng sau cùng. Dòng đầu có n, q, mỗi dòng tiếp theo có l, r.

Ví dụ:

Nhập	In ra
5 2 1 3 2 5	3

Kiểm tra: nhập

10 4
1 10
2 5
4 8
3 3

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Số khách nhiều nhất cùng lúc

Khách sạn có n đơn đặt phòng (n ≤ 10⁵), đơn thứ i ở từ ngày a_i đến hết ngày b_i (1 ≤ a_i ≤ b_i ≤ 10⁶). Hỏi ngày đông nhất có bao nhiêu đơn đang ở?

Ví dụ:

Nhập	In ra
3 1 3 2 5 4 6	2

Kiểm tra: nhập

6
1 4
2 3
3 7
5 6
6 9
3 3

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Sơn tường nhiều lớp

Bức tường dài n ô (n ≤ 10⁶). Có q lần sơn, lần thứ i sơn một lớp lên các ô từ l_i đến r_i. Nhập n, q, k và q đoạn. In ra số ô được sơn đúng k lớp.

Ví dụ:

Nhập	In ra
6 3 2 1 3 2 5 3 4	2

Kiểm tra: nhập

10 5 1
1 4
3 6
8 10
2 2
9 9

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Cộng vào hình chữ nhật

Bảng m × n ban đầu toàn 0 (m, n ≤ 1000, q ≤ 10⁵). Mỗi thao tác cộng v vào hình chữ nhật từ (r1, c1) đến (r2, c2). Dòng đầu có m, n, q, mỗi dòng sau có r1, c1, r2, c2, v. In ra bảng cuối cùng.

Ví dụ:

Nhập	In ra
3 3 1 1 1 2 2 5	5 5 0 5 5 0 0 0 0

Kiểm tra: nhập

3 4 3
1 1 3 4 1
2 2 3 3 2
1 3 1 4 -1

Xem đáp số

1 1 0 0
1 3 3 1
1 3 3 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 17. Đoạn dài nhất có tổng không vượt quá S

Dòng đầu có n, S (n ≤ 10⁵, S ≤ 10¹⁴). Dòng thứ hai có n số nguyên dương (≤ 10⁹). In ra độ dài đoạn liên tiếp dài nhất có tổng ≤ S (in 0 nếu không có).

Ví dụ:

Nhập	In ra
5 7 2 3 1 4 2	3

Kiểm tra: nhập

10 15
5 1 3 5 10 7 4 9 2 8

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Đoạn ngắn nhất có tổng ít nhất S

Dòng đầu có n, S (n ≤ 10⁵, S ≤ 10¹⁴). Dòng thứ hai có n số nguyên dương. In ra độ dài đoạn liên tiếp ngắn nhất có tổng ≥ S (in 0 nếu không có).

Ví dụ:

Nhập	In ra
6 7 2 3 1 2 4 3	2

Kiểm tra: nhập

10 20
1 4 2 10 2 3 1 0 7 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Tổng của mọi đoạn con

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số nguyên dương (≤ 10⁶). In ra tổng của tất cả các tổng đoạn liên tiếp.

Ví dụ:

Nhập	In ra
3 1 2 3	20

Kiểm tra: nhập

6
4 1 7 2 5 3

Xem đáp số

210

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đếm chữ A trong đoạn xâu

Dòng đầu là xâu s gồm chữ in hoa (độ dài ≤ 10⁵). Dòng thứ hai là q. Mỗi dòng trong q dòng tiếp theo có l, r: in ra số chữ A trong đoạn từ ký tự thứ l đến ký tự thứ r.

Ví dụ:

Nhập	In ra
ABRACADABRA 2 1 11 4 8	5 3

Kiểm tra: nhập

BANANAAPPLE
3
1 6
2 7
8 11

Xem đáp số

3
4
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Đoạn có tăng dần không

Dòng đầu có n, q (n, q ≤ 10⁵). Dòng thứ hai có n số nguyên. Mỗi dòng trong q dòng tiếp theo có l, r: in ra YES nếu a_l nhỏ hơn a_{l + 1} nhỏ hơn … nhỏ hơn a_r (tăng ngặt), ngược lại NO.

Ví dụ:

Nhập	In ra
5 2 1 3 2 4 5 1 2 2 4	YES NO

Kiểm tra: nhập

8 4
1 2 5 5 6 8 7 9
1 3
3 4
4 6
1 8

Xem đáp số

YES
NO
YES
NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Khôi phục dãy từ tổng tiền tố

Dòng đầu là n (n ≤ 10⁵). Dòng thứ hai có n số P₁, …, P_n là tổng tiền tố của một dãy a. In ra dãy a.

Ví dụ:

Nhập	In ra
5 3 4 8 9 14	3 1 4 1 5

Kiểm tra: nhập

6
-2 5 5 1 10 0

Xem đáp số

-2 7 0 -4 9 -10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.