Prefix Sum

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

Cộng từng số trong đoạn tốn tới $n$ phép cộng cho một câu hỏi. Với $n = q = 2 \cdot 10^5$, cả bài cỡ $4 \cdot 10^{10}$ phép cộng, quá xa giới hạn một giây.

Đánh số dãy từ 1: $a_1, a_2, \dots, a_n$, và định nghĩa

Mỗi $\mathrm{pre}_i$ là tổng của tiền tố dài $i$. Tổng đoạn $[l, r]$ là tiền tố dài $r$ bỏ đi tiền tố dài $l - 1$:

Hai tiền tố có chung phần $a_1, \dots, a_{l-1}$, phép trừ xóa đúng phần đó. Ô $\mathrm{pre}_0 = 0$ không thừa: nhờ nó, đoạn bắt đầu từ $l = 1$ vẫn dùng chung công thức.

Với $a = (3, 1, 4, 1, 5, 9, 2, 6)$ thì $\mathrm{pre} = (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$.

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

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

Đề. Dãy $n$ số nguyên dương $x_i \le 10^9$ không đổi, $q$ truy vấn $[l, r]$, in tổng đoạn. $n, q \le 2 \cdot 10^5$.

Lời giải. Đúng bài toán của mục này. Dựng $\mathrm{pre}$ khi đọc dãy, mỗi truy vấn in $\mathrm{pre}_r - \mathrm{pre}_{l-1}$. Cả bài $O(n + q)$, tổng lớn nhất cỡ $2 \cdot 10^{14}$ nên dùng 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

XOR và đếm

Công thức $\mathrm{pre}_r - \mathrm{pre}_{l-1}$ chỉ cần hai điều ở phép cộng: kết hợp được, và có phép ngược để gỡ phần đầu ra. Phép toán nào có đủ hai điều đó cũng dựng tiền tố được.

• XOR. Phép XOR, viết $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. Chẳng hạn $5 \oplus 3 = 101_2 \oplus 011_2 = 110_2 = 6$. Đặt $\mathrm{px}_i = a_1 \oplus \dots \oplus a_i$. Vì $x \oplus x = 0$, các phần tử trước $l$ xuất hiện hai lần trong $\mathrm{px}_r \oplus \mathrm{px}_{l-1}$ và tự triệt tiêu, nên XOR đoạn $[l, r]$ là $\mathrm{px}_r \oplus \mathrm{px}_{l-1}$.
• Đếm. Muốn biết đoạn $[l, r]$ có bao nhiêu phần tử thỏa một tính chất (số chẵn, chữ a, ô có cây), đánh dấu $b_i = 1$ nếu phần tử thứ $i$ thỏa, $0$ nếu không, rồi lấy tiền tố của $b$. Với xâu chữ thường, 26 mảng tiền tố cho số lần xuất hiện của từng chữ trong mọi đoạn.

Phép min và max thì không gỡ được: biết số nhỏ nhất của $a_1..a_r$ và của $a_1..a_{l-1}$ không cho biết số nhỏ nhất của $a_l..a_r$. Với các phép này cần công cụ khác: bảng thưa (bài 22) khi dãy không đổi, cây phân đoạn (bài 17) khi dãy bị sửa. Tiền tố của min vẫn có ích khi đoạn luôn bắt đầu từ 1, ví dụ “giá trị nhỏ nhất trong $i$ phần tử đầu”.

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

Đề. Chuỗi $S$ dài $n \le 10^5$ gồm A, C, G, T. Mỗi truy vấn $[l, r]$ hỏi có bao nhiêu chỉ số $i$ với $l \le i < r$ mà $S_i S_{i+1}$ là AC.

Lời giải. Một cặp AC chiếm hai ô nên phải chọn gắn nó với ô nào. Gắn với ô bên phải: đặt $b_i = 1$ nếu $S_{i-1} S_i$ là AC. Cặp nằm trọn trong $[l, r]$ khi ô phải của nó thuộc $[l + 1, r]$, vậy đáp án là $\mathrm{pre}_r - \mathrm{pre}_l$, không phải $\mathrm{pre}_r - \mathrm{pre}_{l-1}$. Viết nhầm thành $l - 1$ sẽ đếm cả cặp vắt qua biên trái, có ô A ở vị trí $l - 1$.

Trên ví dụ AACACGACCT, các cặp có ô phải ở 3, 5, 8. Truy vấn $[2, 5]$ lấy hai ô 3 và 5; truy vấn $[8, 10]$ không lấy ô 8, vì 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

Đếm đoạn con

Nhiều bài hỏi “có bao nhiêu đoạn con thỏa…”. Có $\frac{n(n+1)}{2}$ đoạn, duyệt hết là $O(n^2)$. Mẹo là viết điều kiện của đoạn $[l, r]$ thành điều kiện trên hai số $\mathrm{pre}_{l-1}$ và $\mathrm{pre}_r$, rồi cố định đầu phải $r$ và đếm xem có bao nhiêu chỉ số $j = l - 1 < r$ ghép được với nó.

Bài kinh điển: đếm đoạn có tổng bằng $k$. Điều kiện $\mathrm{pre}_r - \mathrm{pre}_j = k$ tương đương $\mathrm{pre}_j = \mathrm{pre}_r - k$. Duyệt $r$ từ trái sang phải, giữ bảng đếm cnt các giá trị $\mathrm{pre}_0, \dots, \mathrm{pre}_{r-1}$ đã gặp; mỗi đầu phải $r$ góp cnt[pre[r] - k] đoạn. Bảng đếm có sẵn giá trị $\mathrm{pre}_0 = 0$ với số lần 1, chính là tiền tố rỗng ứng với các đoạn bắt đầu từ $l = 1$.

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]++;
}

Thứ tự hai dòng cuối trong vòng lặp quan trọng: phải cộng cnt[cur - k] trước khi thêm cur của chính đầu phải này, nếu không với $k = 0$ ta đếm cả đoạn rỗng $j = r$.

map (bài 09) đếm được theo giá trị bất kỳ, kể cả số âm hay số rất lớn, đổi lại mỗi bước chậm hơn mảng. Khi tiền tố chỉ nhận ít giá trị, ví dụ phần dư khi chia cho $m$, hãy dùng mảng đếm. Chênh lệch lớn hơn ta tưởng:

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

Cùng khuôn đó giải được nhiều điều kiện khác:

• Tổng đoạn chia hết cho $m$: $\mathrm{pre}_r$ và $\mathrm{pre}_j$ cùng số dư khi chia cho $m$, đếm cặp cùng phần dư.
• Tổng đoạn bằng độ dài đoạn: $\mathrm{pre}_r - r = \mathrm{pre}_j - j$, đếm cặp cùng giá trị $\mathrm{pre}_i - i$.
• Tổng đoạn lớn nhất: với mỗi $r$, lấy $\mathrm{pre}_r$ trừ tiền tố nhỏ nhất đứng trước nó; bảng đếm thay bằng một biến giữ tiền tố nhỏ nhất.

Bước khó nhất luôn là biến đổi để một vế chỉ chứa $r$, vế kia chỉ chứa $j$.

Hình dưới chạy trường hợp chia hết trên dữ liệu của ví dụ tiếp theo. Mỗi bước thêm một tiền tố và ghi phần dư của nó khi chia cho 6; cung nối nó với các tiền tố trước cùng dư.

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

Đề. Dãy $N \le 2 \cdot 10^5$ số nguyên, $|A_i| \le 10^9$, có thể âm. Đếm số đoạn con có tổng chia hết cho $N$.

Lời giải. Đoạn $[l, r]$ thỏa khi và chỉ khi $\mathrm{pre}_r - \mathrm{pre}_{l-1}$ chia hết cho $N$, tức hai tiền tố có cùng số dư khi chia cho $N$, nên mỗi cặp tiền tố cùng phần dư ứng với đúng một đoạn. Duyệt $r$, giữ cnt[d] là số tiền tố đứng trước có phần dư $d$, cộng cnt của phần dư hiện tại vào đáp án rồi mới tăng nó. Phần dư chỉ có $N$ giá trị nên dùng mảng, cả bài $O(N)$.

Chỗ dễ sai là số âm: trong C++, -7 % 6 bằng -1 chứ không phải 5, nên phải đưa phần 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ùng số dư rơi vào hai ô khác nhau. Đáp án có thể tới $\frac{N(N+1)}{2} \approx 2 \cdot 10^{10}$, cần long long.

Trên ví dụ, tiền tố là $0, 2, -1, 3, 4, 0, 6$, phần dư theo 6 là $0, 2, 5, 3, 4, 0, 0$. Ba tiền tố dư 0 (vị trí 0, 5, 6) cho ba cặp, ứng với các đoạn $[1, 5]$, $[1, 6]$, $[6, 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

Mảng hiệu

Bài toán ngược lại: dãy ban đầu toàn 0, có $m$ thao tác “cộng $x$ vào mọi phần tử từ $l$ đến $r$”, cuối cùng in dãy. Làm thẳng tốn $O(n)$ mỗi thao tác. Mảng hiệu (difference array) $\mathrm{diff}$ làm mỗi thao tác chỉ bằng hai phép sửa:

Sau mọi thao tác, $a_i = \mathrm{diff}_1 + \dots + \mathrm{diff}_i$, tức $a$ là tổng tiền tố của $\mathrm{diff}$. Một thao tác trên $[l, r]$ làm tổng $\mathrm{diff}_1 + \dots + \mathrm{diff}_i$ tăng $x$ khi $i \ge l$ rồi giảm lại $x$ khi $i \ge r + 1$, nên đúng các vị trí $l \le i \le r$ được cộng $x$. Mảng hiệu và tổng tiền tố là hai phép ngược của nhau.

#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

Mảng diff phải có ô $n + 1$ vì thao tác có $r = n$ sửa tới đó. Kỹ thuật này chỉ dùng được khi mọi thao tác đến trước mọi câu hỏi. Nếu cộng đoạn và hỏi xen kẽ, cần cây Fenwick hoặc cây phân đoạn có cập nhật đoạn.

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

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

Đề. Trên trục $1..2 \cdot 10^5$ có $N$ đoạn. Một điểm nguyên đạt ngưỡng nếu nằm trong ít nhất $K$ đoạn. $Q$ truy vấn $[a, b]$ hỏi đoạn đó chứa bao nhiêu điểm đạt ngưỡng. $N, Q \le 2 \cdot 10^5$.

Lời giải. Hai tầng tiền tố. Tầng một là mảng hiệu cho độ phủ: mỗi đoạn tăng diff[l], giảm diff[r + 1], cộng dồn được số đoạn chứa từng điểm $x$. Tầng hai là tiền tố của dãy đánh dấu “điểm $x$ đạt ngưỡng”, gọi là good. Truy vấn trả lời bằng good[b] - good[a - 1]. Gọi $M = 2 \cdot 10^5$ là độ dài trục, cả bài $O(N + M + Q)$; đếm lại từng điểm cho mỗi truy vấn thì tốn tới $Q \cdot M = 4 \cdot 10^{10}$.

#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

Tiền tố hai chiều

Trên bảng $R \times C$, đặt $P(i, j)$ là tổng hình chữ nhật từ ô $(1, 1)$ tới ô $(i, j)$, với hàng 0 và cột 0 bằng 0. Mỗi ô tính từ ba ô đã có:

Hai hình $P(i-1, j)$ và $P(i, j-1)$ cùng chứa phần $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 hình chữ nhật từ hàng $r_1$ tới $r_2$, cột $c_1$ tới $c_2$ ghép theo cùng cách nghĩ, gọi là bao hàm loại trừ: lấy hình lớn, trừ hai dải thừa, rồi cộng lại góc bị trừ hai lần:

Dựng bảng tốn $O(RC)$, mỗi câu hỏi $O(1)$. Mảng hiệu cũng có bản hai chiều: cộng $x$ lên một hình chữ nhật bằng cách sửa bốn góc, $+x$ tại $(r_1, c_1)$ và $(r_2 + 1, c_2 + 1)$, $-x$ tại $(r_1, c_2 + 1)$ và $(r_2 + 1, c_1)$, rồi lấy tiền tố hai chiều một lần ở cuối.

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

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

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

Đề. Lưới $n \times n$ ($n \le 1000$), ô * có cây. $q \le 2 \cdot 10^5$ truy vấn, mỗi truy vấn cho góc trên-trái và góc dưới-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à 1, ô trống là 0, dựng $P$ theo công thức trên rồi trả lời bằng bốn góc. Dựng $O(n^2) = 10^6$, mỗi truy vấn $O(1)$. Tên biến cho góc tránh y1: trong <cmath> đã có hàm tên đó, khai báo biến toàn cục trùng tên sẽ 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