Prefix Sum

ITổng đoạn bằng một phép trừ

Đánh số dãy từ $1$: $a_1, a_2, \dots, a_n$. Đoạn gồm các vị trí từ $l$ tới $r$ được viết là $[l, r]$.

Cách dễ nghĩ ra nhất là với mỗi câu hỏi, cộng lần lượt các số từ $a_l$ tới $a_r$:

while (q--) {
    ll l, r, sum = 0;
    cin >> l >> r;
    for (ll i = l; i <= r; i++) sum += a[i];
    cout << sum << '\n';
}

Độ phức tạp: $O(nq)$, với $n = q = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^{10}$ phép tính.

Mỗi câu hỏi có thể phải cộng tới $n$ số, nên cả bài vượt xa khoảng $10^8$ phép tính mà máy chấm làm được trong một giây. Ta có thể thấy được điểm lãng phí của cách làm trên: các câu hỏi khác nhau thường có phần chung, chẳng hạn hai câu hỏi $[2, 7]$ và $[3, 9]$ cùng chứa $a_3 + a_4 + \dots + a_7$, nhưng câu hỏi nào cũng cộng lại phần đó từ đầu.

Thay vào đó, ta cộng một lần trước khi đọc câu hỏi. Gọi $i$ số đầu tiên của dãy là tiền tố dài $i$, và gọi tổng của chúng là $\mathrm{pre}_i$:

Mảng $\mathrm{pre}$ được gọi là mảng tiền tố (hay mảng cộng dồn). Nhờ công thức $\mathrm{pre}_i = \mathrm{pre}_{i-1} + a_i$, ta dựng được cả mảng trong một lượt duyệt. Tiền tố dài $r$ gồm tiền tố dài $l - 1$ và đoạn $[l, r]$ đứng nối tiếp nhau, nên tổng của đoạn bằng hiệu hai tổng tiền tố:

Ô $\mathrm{pre}_0 = 0$ là tổng của tiền tố không có số nào. Nhờ ô này, công thức vẫn đúng với các đoạn bắt đầu từ $l = 1$.

Ví dụ với dãy $3, 1, 4, 1, 5, 9, 2, 6$, mảng tiền tố là $0, 3, 4, 8, 9, 14, 23, 25, 31$. Tổng đoạn $[3, 6]$ là $4 + 1 + 5 + 9 = 19$, đúng bằng $\mathrm{pre}_6 - \mathrm{pre}_2 = 23 - 4$. Bạn có thể kéo hai đầu $l$, $r$ để thử với các đoạn khác:

Công thức ngắn, nhưng có hai chỗ hay viết sai. Chỗ thứ nhất là kiểu dữ liệu: mỗi $a_i$ có thể vừa kiểu int, nhưng tổng của $2 \cdot 10^5$ số cỡ $10^9$ lên tới $2 \cdot 10^{14}$, nên mảng tiền tố cần kiểu long long. Chỗ thứ hai là chỉ số: nếu đọc dãy vào a[0] tới a[n - 1] mà vẫn dùng công thức $\mathrm{pre}_r - \mathrm{pre}_{l-1}$, mọi câu trả lời đều lệch một vị trí. Cách an toàn là cho mảng tiền tố $n + 1$ ô và luôn hiểu $\mathrm{pre}_i$ là tổng của $i$ số đầu tiên.

Ví dụTổng Trên Đoạn Cố Định

Đề. Cho dãy $n$ số nguyên dương $x_1, x_2, \dots, x_n$ ($x_i \le 10^9$) và $q$ câu hỏi; mỗi câu hỏi cho $l, r$ và hỏi tổng các số từ vị trí $l$ đến vị trí $r$ ($n, q \le 2 \cdot 10^5$).

Lời giải. Đây đúng là bài toán của mục này. Ta dựng mảng tiền tố ngay khi đọc dãy, rồi với mỗi câu hỏi in $\mathrm{pre}_r - \mathrm{pre}_{l-1}$. Tổng lớn nhất có thể tới $2 \cdot 10^{14}$, nên cần dùng kiểu long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, q, a[N], pre[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
}

ChạyInput7 4
4 2 7 1 3 5 6
1 1
2 5
4 7
1 7

Output4
13
15
28

Độ phức tạp: $O(n + q)$, với $n = q = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

IIĐếm phần tử thỏa điều kiện trên đoạn

Bài toán: cho dãy $n$ số và nhiều câu hỏi, mỗi câu hỏi đoạn $[l, r]$ có bao nhiêu số chẵn.

Ta đổi bài toán này về bài tính tổng đoạn. Đánh dấu $b_i = 1$ nếu $a_i$ là số chẵn và $b_i = 0$ nếu $a_i$ là số lẻ. Khi đó số số chẵn trong đoạn $[l, r]$ chính là tổng $b_l + b_{l+1} + \dots + b_r$, nên ta chỉ cần dựng mảng tiền tố của dãy $b$.

Cách làm này dùng được cho mọi điều kiện xét riêng trên từng phần tử: số chẵn, số dương, ô có cây, ký tự là chữ a. Với một chuỗi chữ cái thường mà câu hỏi có thể hỏi về chữ cái bất kỳ, ta dựng $26$ mảng tiền tố, mỗi mảng cho một chữ cái.

Ví dụĐếm Cặp AC Trên Đoạn

Đề. Cho chuỗi $S$ dài $n \le 10^5$ chỉ gồm các chữ A, C, G, T, và $q \le 10^5$ câu hỏi. Mỗi câu hỏi cho $l, r$ và hỏi có bao nhiêu vị trí $i$ với $l \le i < r$ mà hai ký tự $S_i S_{i+1}$ là AC.

Lời giải. Mỗi cặp AC chiếm hai vị trí liền nhau, nên ta cần chọn đánh dấu cặp vào một trong hai vị trí đó. Ta đánh dấu vào vị trí của chữ C, tức là vị trí bên phải: $b_i = 1$ nếu $S_{i-1} S_i$ là AC. Một cặp nằm trọn trong đoạn $[l, r]$ khi chữ C của nó nằm ở vị trí từ $l + 1$ tới $r$, nên đáp án là $\mathrm{pre}_r - \mathrm{pre}_l$ chứ không phải $\mathrm{pre}_r - \mathrm{pre}_{l-1}$. Nếu viết $\mathrm{pre}_{l-1}$, ta sẽ đếm thừa cặp có chữ A ở vị trí $l - 1$, nằm ngoài đoạn.

Trên chuỗi AACACGACCT, chữ C của các cặp AC nằm ở vị trí $3, 5, 8$. Câu hỏi $[2, 5]$ đếm được hai cặp, ứng với vị trí $3$ và $5$. Câu hỏi $[8, 10]$ không đếm cặp nào: cặp có chữ C ở vị trí $8$ có chữ A ở vị trí $7$, nằm ngoài đoạn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, q, pre[N];
string s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> s;
    s = " " + s;
    for (ll i = 1; i <= n; i++) pre[i] = pre[i - 1] + (i > 1 && s[i - 1] == 'A' && s[i] == 'C');
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l] << '\n';
    }
}

ChạyInput10 5
AACACGACCT
1 10
2 5
3 7
5 8
8 10

Output3
2
1
1
0

Độ phức tạp: $O(n + q)$, với $n = q = 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

IIIPhép toán nào dùng được tiền tố

Công thức $\mathrm{pre}_r - \mathrm{pre}_{l-1}$ đúng nhờ hai điều. Thứ nhất, tổng của tiền tố dài $r$ ghép được từ tổng của tiền tố dài $l - 1$ và tổng của đoạn $[l, r]$. Thứ hai, phép trừ là phép ngược của phép cộng, nên gỡ được phần tiền tố dài $l - 1$ ra. Một phép toán khác cũng dùng được tiền tố nếu nó có đủ hai điều đó, nghĩa là có một phép ngược để gỡ phần đầu ra.

Phép XOR. Phép XOR của hai số, viết là $x \oplus y$ và trong C++ là x ^ y, so hai số theo từng chữ số nhị phân: hai chữ số khác nhau cho $1$, giống nhau cho $0$. Ví dụ $5 \oplus 3 = 101_2 \oplus 011_2 = 110_2 = 6$. Vì $x \oplus x = 0$, phép XOR là phép ngược của chính nó. Đặt $X_0 = 0$ và $X_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$. Trong $X_r \oplus X_{l-1}$, mỗi số đứng trước vị trí $l$ xuất hiện hai lần và tự triệt tiêu, nên XOR của đoạn $[l, r]$ bằng $X_r \oplus X_{l-1}$.

Phép min, max. Biết số nhỏ nhất của $a_1, \dots, a_r$ và số nhỏ nhất của $a_1, \dots, a_{l-1}$ không cho ta biết số nhỏ nhất của đoạn $[l, r]$, vì số nhỏ nhất của tiền tố dài $r$ có thể nằm ngay trong phần đầu cần bỏ đi. Vì vậy tiền tố không trả lời được câu hỏi về số nhỏ nhất hay lớn nhất trên một đoạn bất kỳ. Tiền tố min vẫn có ích khi đoạn luôn bắt đầu từ vị trí $1$, chẳng hạn “số nhỏ nhất trong $i$ số đầu tiên”.

Sử dụng kiến thức này cũng có thể giải bài: với mỗi vị trí $i$, tính ước chung lớn nhất của các số còn lại khi bỏ đi riêng $a_i$. Phép lấy ước chung lớn nhất cũng không có phép ngược, nhưng ở đây phần còn lại gồm một tiền tố và một hậu tố (các số ở cuối dãy). Ta tính ước chung lớn nhất của mọi tiền tố từ trái sang và của mọi hậu tố từ phải sang. Đáp án tại vị trí $i$ là ước chung lớn nhất của hai số: một số của tiền tố $a_1, \dots, a_{i-1}$, một số của hậu tố $a_{i+1}, \dots, a_n$.

IVĐếm đoạn có tổng bằng k

Bài toán: cho dãy $n$ số nguyên, có thể âm, và một số $k$. Đếm số đoạn $[l, r]$ có tổng bằng $k$.

Dãy có $\frac{n(n+1)}{2}$ đoạn. Có mảng tiền tố, ta tính được tổng mỗi đoạn bằng một phép trừ, nhưng thử hết mọi đoạn vẫn tốn $O(n^2)$, khoảng $2 \cdot 10^{10}$ phép tính khi $n = 2 \cdot 10^5$.

Viết điều kiện bằng mảng tiền tố: đoạn $[l, r]$ có tổng bằng $k$ khi $\mathrm{pre}_r - \mathrm{pre}_{l-1} = k$, tức là $\mathrm{pre}_{l-1} = \mathrm{pre}_r - k$. Đặt $j = l - 1$, mỗi đoạn $[l, r]$ ứng với đúng một cặp chỉ số $j < r$ (với $j$ có thể bằng $0$) thỏa $\mathrm{pre}_j = \mathrm{pre}_r - k$, và ngược lại. Vì vậy thay vì đếm đoạn, ta đếm các cặp chỉ số như vậy.

Ta duyệt $r$ từ $1$ tới $n$ và giữ một bảng đếm: với mỗi giá trị $v$, bảng ghi có bao nhiêu chỉ số $j < r$ mà $\mathrm{pre}_j = v$. Tại mỗi $r$, số đoạn kết thúc tại $r$ có tổng bằng $k$ chính là số mà bảng ghi cho giá trị $\mathrm{pre}_r - k$. Sau đó ta thêm $\mathrm{pre}_r$ vào bảng để dùng cho các $r$ phía sau. Lúc bắt đầu, bảng đã có sẵn giá trị $\mathrm{pre}_0 = 0$ một lần, ứng với các đoạn bắt đầu từ $l = 1$.

Tiền tố có thể âm hoặc rất lớn, nên không dùng trực tiếp làm chỉ số của mảng được. Ta dùng map<ll, ll>, có thể hiểu như một mảng đếm mà chỉ số là số nguyên bất kỳ. Trong code, ta không cần lưu cả mảng tiền tố, vì ở mỗi bước chỉ dùng tiền tố của vị trí đang xét:

map<ll, ll> cnt;
cnt[0] = 1;
ll cur = 0, ans = 0;
for (ll i = 1; i <= n; i++) {
    cur += a[i];
    ans += cnt[cur - k];
    cnt[cur]++;
}

Độ phức tạp: $O(n \log n)$ vì mỗi lần dùng map tốn $O(\log n)$; với $n = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^6$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, k, a[N];

signed main() {
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    map<ll, ll> cnt;
    cnt[0] = 1;
    ll cur = 0, ans = 0;
    for (ll i = 1; i <= n; i++) {
        cur += a[i];
        cnt[cur]++;
        ans += cnt[cur - k];
    }
    cout << ans << '\n';
}

ChạyInput3 0
1 -1 0

Output6

Khi tiền tố chỉ nhận ít giá trị, chẳng hạn phần dư khi chia cho một số $m$ nhỏ, ta nên dùng mảng đếm thay cho map. Chênh lệch tốc độ lớn hơn ta tưởng:

Cùng một vòng lặp, chỉ khác bảng đếm, mà map chậm hơn mảng khoảng $27$ lần, còn unordered_map chậm hơn khoảng $8$ lần. Với $n = 2 \cdot 10^5$, cả ba cách đều kịp thời gian, nhưng khi giới hạn chặt, đó có thể là khác biệt giữa AC và TLE.

Ví dụĐếm Đoạn Có Tổng Chia Hết

Đề. Cho dãy $N \le 2 \cdot 10^5$ số nguyên $A_1, \dots, A_N$ với $|A_i| \le 10^9$, có thể âm. Đếm số đoạn có tổng chia hết cho $N$.

Lời giải. Đoạn $[l, r]$ có tổng chia hết cho $N$ khi $\mathrm{pre}_r - \mathrm{pre}_{l-1}$ chia hết cho $N$, tức là hai tiền tố $\mathrm{pre}_r$ và $\mathrm{pre}_{l-1}$ có cùng số dư khi chia cho $N$. Như vậy mỗi cặp tiền tố có cùng số dư ứng với đúng một đoạn cần đếm. Ta duyệt $r$ và giữ một mảng đếm: với mỗi số dư, có bao nhiêu tiền tố đứng trước có số dư đó. Tại mỗi $r$, cộng số tiền tố có cùng số dư với $\mathrm{pre}_r$ vào đáp án, rồi mới thêm $\mathrm{pre}_r$ vào mảng đếm. Số dư chỉ có $N$ giá trị nên dùng mảng được, và cả bài tốn $O(N)$.

Cần cẩn thận với số âm: trong C++, -7 % 6 bằng -1 chứ không phải 5. Vì vậy ta đưa số dư về khoảng từ $0$ tới $N - 1$ bằng ((x % n) + n) % n; nếu không, hai tiền tố có cùng số dư có thể rơi vào hai ô khác nhau của mảng đếm. Đáp án có thể tới $\frac{N(N+1)}{2} \approx 2 \cdot 10^{10}$, nên cần dùng kiểu long long cho kết quả.

Trên ví dụ của đề, các tiền tố là $0, 2, -1, 3, 4, 0, 6$, và số dư của chúng khi chia cho $6$ là $0, 2, 5, 3, 4, 0, 0$. Ba tiền tố có số dư $0$, ở các vị trí $0, 5, 6$, tạo thành ba cặp, ứng với ba đoạn $[1, 5]$, $[1, 6]$ và $[6, 6]$. Mỗi cung trong hình dưới nối hai tiền tố có cùng số dư, tức là một đoạn có tổng chia hết cho $6$:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, cnt[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cnt[0] = 1;
    ll cur = 0, ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        cur = ((cur + x) % n + n) % n;
        ans += cnt[cur];
        cnt[cur]++;
    }
    cout << ans << '\n';
}

ChạyInput6
2 -3 4 1 -4 6

Output3

Độ phức tạp: $O(N)$, với $N = 2 \cdot 10^5$ cần khoảng $2 \cdot 10^5$ phép tính.

Bước khó nhất của các bài đếm đoạn thường là biến đổi điều kiện, sao cho một vế chỉ chứa những gì của vị trí $r$, vế còn lại chỉ chứa những gì của vị trí $l - 1$. Câu hỏi dưới đây là một ví dụ.

Sử dụng kiến thức này cũng có thể giải bài: tìm đoạn có tổng lớn nhất. Với mỗi $r$, đoạn có tổng lớn nhất kết thúc tại $r$ có tổng bằng $\mathrm{pre}_r$ trừ đi tiền tố nhỏ nhất trong $\mathrm{pre}_0, \dots, \mathrm{pre}_{r-1}$. Thay cho bảng đếm, ta chỉ cần giữ một biến lưu tiền tố nhỏ nhất đã gặp.

VCộng cả đoạn: mảng hiệu

Bài toán: dãy $a_1, a_2, \dots, a_n$ ban đầu toàn số $0$. Có $m$ thao tác, mỗi thao tác cộng $x$ vào mọi số từ vị trí $l$ đến vị trí $r$. In dãy sau khi làm hết các thao tác.

Làm thẳng mỗi thao tác tốn tới $n$ phép cộng, nên cả bài tốn $O(nm)$. Ta có thể làm mỗi thao tác chỉ bằng hai phép sửa. Giữ một mảng $\mathrm{diff}$, ban đầu toàn số $0$, gọi là mảng hiệu (difference array). Mỗi thao tác cộng $x$ vào đoạn $[l, r]$ chỉ sửa hai ô của mảng này:

Sau khi làm hết các thao tác, ta lấy tổng tiền tố của mảng hiệu, và đó chính là dãy cần in: $a_i = \mathrm{diff}_1 + \mathrm{diff}_2 + \dots + \mathrm{diff}_i$. Tên gọi mảng hiệu đến từ việc $\mathrm{diff}_i = a_i - a_{i-1}$: mảng hiệu và mảng tiền tố là hai phép ngược của nhau.

Hình dưới chạy ba thao tác của chương trình ngay sau đó: mỗi thao tác chỉ sửa hai ô, và một lượt cộng dồn ở cuối cho lại cả dãy.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, m, diff[N];

signed main() {
    cin >> n >> m;
    while (m--) {
        ll l, r, x;
        cin >> l >> r >> x;
        diff[l] += x;
        diff[r + 1] -= x;
    }
    ll cur = 0;
    for (ll i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << (i == n ? '\n' : ' ');
    }
}

ChạyInput8 3
2 5 2
4 7 3
1 3 -1

Output-1 1 1 5 5 3 3 0

Độ phức tạp: $O(n + m)$, với $n = m = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

Mảng hiệu cần có ô thứ $n + 1$, vì thao tác có $r = n$ sẽ sửa tới ô đó. Ngoài ra, cách làm này chỉ dùng được khi mọi thao tác cộng đều đến trước mọi câu hỏi. Nếu thao tác cộng và câu hỏi xen kẽ nhau, mỗi lần hỏi ta lại phải cộng dồn cả mảng, và cần một cách làm khác.

Mảng hiệu hay xuất hiện ở dạng độ phủ: trên trục số có nhiều đoạn, hỏi mỗi điểm nằm trong bao nhiêu đoạn. Mỗi đoạn $[l, r]$ là một thao tác cộng $1$ vào các điểm từ $l$ tới $r$, nên một lượt cộng dồn ở cuối cho độ phủ của mọi điểm.

Ví dụĐiểm Đạt Ngưỡng

Đề. Trên trục số có $N$ đoạn với hai đầu mút là số nguyên từ $1$ tới $2 \cdot 10^5$. Một điểm nguyên gọi là đạt ngưỡng nếu nó nằm trong ít nhất $K$ đoạn. Có $Q$ câu hỏi, mỗi câu hỏi cho $a, b$ và hỏi đoạn $[a, b]$ chứa bao nhiêu điểm đạt ngưỡng ($N, Q \le 2 \cdot 10^5$).

Lời giải. Bài này dùng tiền tố hai lần. Lần thứ nhất là mảng hiệu để tính độ phủ: mỗi đoạn trong đề là một thao tác cộng $1$, và một lượt cộng dồn cho biết mỗi điểm nằm trong bao nhiêu đoạn. Lần thứ hai giống mục Đếm phần tử thỏa điều kiện trên đoạn: đánh dấu $1$ cho các điểm đạt ngưỡng, dựng mảng tiền tố của dãy đánh dấu đó, rồi mỗi câu hỏi $[a, b]$ được trả lời bằng một phép trừ.

Gọi $M = 2 \cdot 10^5$ là độ dài trục số. Nếu đếm lại từng điểm cho mỗi câu hỏi, cả bài có thể tốn tới $Q \cdot M = 4 \cdot 10^{10}$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll M = 2e5;
ll n, k, q, diff[M + 5], good[M + 5];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> q;
    for (ll i = 1; i <= n; i++) {
        ll l, r;
        cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }
    ll cover = 0;
    for (ll x = 1; x <= M; x++) {
        cover += diff[x];
        good[x] = good[x - 1] + (cover >= k);
    }
    while (q--) {
        ll a, b;
        cin >> a >> b;
        cout << good[b] - good[a - 1] << '\n';
    }
}

ChạyInput4 3 5
1 5
3 7
4 9
6 10
1 10
3 6
5 8
1 3
7 10

Output4
3
3
0
1

Độ phức tạp: $O(N + M + Q)$, với $N = Q = M = 2 \cdot 10^5$ cần khoảng $6 \cdot 10^5$ phép tính.

VITổng hình chữ nhật: tiền tố hai chiều

Bài toán: cho một bảng số có $R$ hàng, $C$ cột, và nhiều câu hỏi. Mỗi câu hỏi tổng các số trong một hình chữ nhật con, từ hàng $r_1$ tới hàng $r_2$ và từ cột $c_1$ tới cột $c_2$.

Gọi $P(i, j)$ là tổng các số trong hình chữ nhật từ ô $(1, 1)$ tới ô $(i, j)$, và quy ước hàng $0$, cột $0$ đều bằng $0$. Mỗi ô của $P$ tính được từ ba ô đã có:

Hai hình chữ nhật ứng với $P(i-1, j)$ và $P(i, j-1)$ cùng chứa phần ứng với $P(i-1, j-1)$, nên phần đó bị cộng hai lần và phải trừ đi một lần. Tổng của hình chữ nhật cần hỏi cũng tính theo cùng cách nghĩ: lấy hình lớn từ ô $(1, 1)$ tới ô $(r_2, c_2)$, trừ đi hai dải thừa ở phía trên và bên trái, rồi cộng lại phần góc trên bên trái bị trừ hai lần:

Cách cộng trừ như vậy được gọi là bao hàm loại trừ (inclusion-exclusion). Bạn có thể kéo chuột trên bảng để chọn hình chữ nhật khác:

Dựng bảng $P$ tốn $O(RC)$, sau đó mỗi câu hỏi chỉ tốn $O(1)$.

Hai vòng lặp dựng bảng đổi chỗ cho nhau thì công thức vẫn đúng, và độ phức tạp vẫn là $O(RC)$. Tuy nhiên tốc độ thật thì khác: mảng hai chiều trong C++ được lưu liền nhau theo từng hàng, nên để cột $j$ ở vòng trong là đọc các ô nằm sát nhau trong bộ nhớ, còn để hàng $i$ ở vòng trong thì mỗi bước phải nhảy qua cả một hàng.

Cùng $9 \cdot 10^6$ phép tính, nhưng cách để hàng ở vòng trong chậm hơn gần ba lần. Quy tắc dễ nhớ: chỉ số cuối cùng của mảng nên nằm ở vòng lặp trong cùng.

Sử dụng kiến thức này cũng có thể giải bài: cộng $x$ vào nhiều hình chữ nhật rồi in cả bảng, bằng mảng hiệu hai chiều. Mỗi hình chữ nhật chỉ sửa bốn ô: cộng $x$ tại $(r_1, c_1)$ và $(r_2 + 1, c_2 + 1)$, trừ $x$ tại $(r_1, c_2 + 1)$ và $(r_2 + 1, c_1)$. Cuối cùng, ta lấy tiền tố hai chiều của cả bảng một lần.

Ví dụĐếm Cây Trong Hình Chữ Nhật

Đề. Cho lưới $n \times n$ ($n \le 1000$), ô * có cây, ô . trống. Có $q \le 2 \cdot 10^5$ câu hỏi, mỗi câu hỏi cho góc trên bên trái và góc dưới bên phải của một hình chữ nhật, hỏi có bao nhiêu cây bên trong.

Lời giải. Coi ô có cây là số $1$, ô trống là số $0$, dựng bảng $P$ theo công thức trên rồi trả lời mỗi câu hỏi bằng bốn góc. Cần chú ý khi đặt tên biến cho tọa độ góc: không nên dùng tên y1, vì thư viện <cmath> đã có một hàm trùng tên, khai báo biến toàn cục tên y1 sẽ gây lỗi biên dịch.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1005;
ll n, q, p[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (ll j = 1; j <= n; j++) p[i][j] = (s[j - 1] == '*') + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
    }
    while (q--) {
        ll r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << p[r2][c2] - p[r1 - 1][c2] - p[r2][c1 - 1] + p[r1 - 1][c1 - 1] << '\n';
    }
}

+11 dòngChạyInput5 5
.*..*
**...
..*..
*..**
...*.
1 1 1 5
1 1 5 5
2 2 4 4
3 3 3 3
4 4 5 5

Output2
9
3
1
3

Độ phức tạp: $O(n^2 + q)$, với $n = 1000$ và $q = 2 \cdot 10^5$ cần khoảng $1{,}2 \cdot 10^6$ phép tính.