Prefix Sum

Tổng của một đoạn bằng hiệu hai tiền tố

Đánh số dãy từ 1: $a_1, a_2, \dots, a_n$. Đị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$:

Đẳng thức đúng vì $\mathrm{pre}_r$ gồm $a_1, \dots, a_{l-1}$ và $a_l, \dots, a_r$; phép trừ xóa đúng phần đầu. Ô $\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 $\mathrm{pre}_r - \mathrm{pre}_0$.

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

Hai chỗ hay sai nằm ngay trong công thức ngắn này. Thứ nhất là kiểu dữ liệu: mỗi $a_i$ vừa 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 $\mathrm{pre}$ phải là long long. Thứ 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 là để $\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;
using 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';
    }
}

Input7 4
4 2 7 1 3 5 6
1 1
2 5
4 7
1 7

Output4
13
15
28

Không chỉ là phép cộng

Công thức $\mathrm{pre}_r - \mathrm{pre}_{l-1}$ chỉ dùng hai tính chất của 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 tính chất đó 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, ký tự a, ô có cây), dựng tiền tố của dãy đánh dấu $b_i$, bằng 1 nếu phần tử thứ $i$ thỏa và 0 nếu không. Với chuỗi chữ thường, 26 mảng tiền tố cho tần suất 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;
using 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';
    }
}

Input10 5
AACACGACCT
1 10
2 5
3 7
5 8
8 10

Output3
2
1
1
0

Đếm đoạn con: chuyển về cặp tiền tố

Rất 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ó.

Ví dụ 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) là bảng đếm 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$) thì dùng mảng đếm.

Cùng khuôn đó giải được nhiều điều kiện khác. Tổng đoạn chia hết cho $m$ khi $\mathrm{pre}_r$ và $\mathrm{pre}_j$ có 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 khi $\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ó, rồi lấy lớn nhất qua mọi $r$; thay bảng đếm 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$.

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;
using 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';
}

Input6
2 -3 4 1 -4 6

Output3

Mảng hiệu: cộng cả đoạn chỉ bằng hai phép sửa

Bài toán ngược: 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 trong $O(1)$:

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;
using 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' : ' ');
    }
}

Input8 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;
using 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';
    }
}

Input4 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

Tổng 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.

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;
using 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òngInput5 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