Sqrt Decomposition

Khối

Chọn độ dài khối $B$, đánh số từ 1 và đặt id[i] = (i - 1) / B. Mỗi khối $k$ giữ một giá trị gộp, chẳng hạn tổng s[k]. Câu hỏi $[l, r]$ nằm trong một khối thì duyệt thẳng; ngược lại tách thành mảnh trái từ $l$ tới hết khối của $l$, các khối nguyên ở giữa, và mảnh phải từ đầu khối của $r$ tới $r$. Hai mảnh có không quá $2B$ phần tử, giữa có không quá $n / B$ khối, nên mỗi câu hỏi tốn $O(B + n / B)$.

Tổng hai số hạng nhỏ nhất khi $B = \sqrt n$, còn $2\sqrt n$. Với $n = 2 \cdot 10^5$ là khoảng 900 phép mỗi câu.

Gán $a_p = x$ chỉ làm đổi tổng một khối: s[id[p]] += x - a[p], $O(1)$. Fenwick làm được việc này nhanh hơn, nhưng khung khối là thứ ta dùng lại ở mọi mục sau.

Ví dụTổng Đoạn Linh Hoạt

Đề. Dãy $n \le 2 \cdot 10^5$ số, $q \le 2 \cdot 10^5$ thao tác: gán $a_p = x$, hoặc in tổng $a_l + \dots + a_r$.

Lời giải. Chia dãy thành các khối dài $B = \lfloor \sqrt n \rfloor$ và giữ tổng của mỗi khối. Một đoạn bất kỳ gồm tối đa hai mảnh biên lẻ và một dãy khối nằm trọn, mỗi phần tối đa $\sqrt n$ bước.

Bước 1: chia khối. id[i] = (i - 1) / B là khối của vị trí $i$; s[k] là tổng khối $k$, cộng dồn ngay khi đọc.

B = max(1LL, (ll)sqrt(n));
for (ll i = 1; i <= n; i++) {
    cin >> a[i];
    id[i] = (i - 1) / B;
    s[id[i]] += a[i];
}

Bước 2: tổng một đoạn. Cùng khối thì cộng thẳng. Khác khối thì ba phần: vòng đầu chạy từ $l$ tới hết khối của $l$, vòng giữa cộng tổng các khối nằm trọn, vòng cuối chạy lùi từ $r$ tới đầu khối của $r$.

ll get(ll l, ll r) {
    ll res = 0;
    if (id[l] == id[r]) {
        for (ll i = l; i <= r; i++) res += a[i];
        return res;
    }
    for (ll i = l; id[i] == id[l]; i++) res += a[i];
    for (ll k = id[l] + 1; k < id[r]; k++) res += s[k];
    for (ll i = r; id[i] == id[r]; i--) res += a[i];
    return res;
}

Bước 3: gán một phần tử. Sửa tổng khối bằng phần chênh y - a[x] rồi mới ghi giá trị mới, $O(1)$.

s[id[x]] += y - a[x];
a[x] = y;

Tổng có thể tới $2 \cdot 10^{14}$, phải dùng ll.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 5;
ll n, q, B, a[N], id[N], s[N];

ll get(ll l, ll r) {
    ll res = 0;
    if (id[l] == id[r]) {
        for (ll i = l; i <= r; i++) res += a[i];
        return res;
    }
    for (ll i = l; id[i] == id[l]; i++) res += a[i];
    for (ll k = id[l] + 1; k < id[r]; k++) res += s[k];
    for (ll i = r; id[i] == id[r]; i--) res += a[i];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        s[id[i]] += a[i];
    }
    while (q--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            s[id[x]] += y - a[x];
            a[x] = y;
        } else cout << get(x, y) << '\n';
    }
}

ChạyInput5 5
2 1 3 4 5
2 2 5
1 3 10
2 1 3
1 5 6
2 4 5

Output13
13
10

Độ phức tạp: gán $O(1)$, câu hỏi $O(\sqrt n)$.

Chọn $B$ đúng thật sự quan trọng:

Khối quá ngắn chậm gấp khoảng 8 lần, khối quá dài chậm gấp khoảng 27 lần so với $B = \sqrt n$. Chọn $B$ cho hai phía bằng nhau.

Nhãn khối

Cộng $c$ vào cả một đoạn cũng dùng cách tách ấy. Khối nguyên chỉ ghi vào nhãn chung tag[k], nghĩa là “mọi phần tử của khối còn phải cộng thêm tag[k]”. Phần tử ở hai mảnh biên sửa trực tiếp. Giá trị thật của $a_i$ là a[i] + tag[id[i]], và mỗi cập nhật cũng $O(B + n / B)$.

Nhãn có thể là phép cộng, phép gán, hay cặp (nhân, cộng) cho hàm $x \mapsto bx + c$. Khi sửa lẻ một phần tử của khối đang mang nhãn không giao hoán với phép sửa, áp nhãn xuống cả khối trước.

Khối giữ dữ liệu đã sắp. Để đếm trên đoạn số phần tử nhỏ hơn $x$, mỗi khối giữ thêm một bản sao đã sắp các giá trị của nó. Cộng cả khối không đổi thứ tự trong khối, nên chỉ cần tăng nhãn; khối nguyên trả lời bằng một lần lower_bound với $x - \mathrm{tag}$. Mảnh biên bị sửa thì sắp lại khối đó, tốn $O(B \log B)$. Phần giữa tốn $(n / B) \log B$ cho các lần chặt nhị phân, nên hai phía vẫn cân ở $B = \sqrt n$. Nếu phần giữa chỉ tốn $n / B$ thì nên chọn $B = \sqrt{n / \log n}$. Ước lượng hai phía rồi chọn $B$ cho chúng bằng nhau.

Ví dụBao Nhiêu Số Bé Hơn

Đề. Dãy $n \le 5 \cdot 10^4$ số và $n$ thao tác: cộng $c$ vào đoạn $[l, r]$, hoặc đếm trên $[l, r]$ số phần tử nhỏ hơn hẳn $c^2$.

Lời giải. Mỗi khối giữ nhãn cộng tag[k] và vector v[k] các giá trị gốc của khối đã sắp (chưa cộng nhãn). Cộng vào cả khối không làm đổi thứ tự trong khối, nên chỉ tăng nhãn; chỉ mảnh biên mới làm thứ tự đổi và phải sắp lại. Phần tử của khối nằm trọn nhỏ hơn $w$ khi giá trị gốc nhỏ hơn $w - \mathrm{tag}$, đếm bằng một lần lower_bound. $c$ tới $2^{31}$ nên $c^2$ tới $2^{62}$, vẫn vừa ll.

Bước 1: dựng lại một khối. L[k], R[k] là vị trí đầu, cuối của khối; rebuild chép các giá trị gốc rồi sắp, $O(B \log B)$.

void rebuild(ll k) {
    v[k].clear();
    for (ll i = L[k]; i <= R[k]; i++) v[k].push_back(a[i]);
    sort(v[k].begin(), v[k].end());
}

Bước 2: mảnh biên. add chỉ được gọi cho một mảnh nằm trong một khối: sửa a[i] rồi dựng lại khối đó. calc đếm thẳng trên mảnh biên, so giá trị thật a[i] + tag với ngưỡng.

void add(ll l, ll r, ll c) {
    for (ll i = l; i <= r; i++) a[i] += c;
    rebuild(id[l]);
}

ll calc(ll l, ll r, ll x) {
    ll res = 0;
    for (ll i = l; i <= r; i++) res += (a[i] + tag[id[i]] < x);
    return res;
}

Bước 3: hai loại thao tác. Cộng: hai mảnh biên qua add, khối giữa tăng tag. Đếm: hai mảnh biên qua calc, khối giữa đếm bằng lower_bound trên v[k] với ngưỡng đã trừ nhãn.

for (ll k = id[x] + 1; k < id[y]; k++)
    res += lower_bound(v[k].begin(), v[k].end(), w - tag[k]) - v[k].begin();

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 5e4 + 5;
ll n, B, a[N], id[N], L[N], R[N], tag[N];
vector<ll> v[N];

void rebuild(ll k) {
    v[k].clear();
    for (ll i = L[k]; i <= R[k]; i++) v[k].push_back(a[i]);
    sort(v[k].begin(), v[k].end());
}

void add(ll l, ll r, ll c) {
    for (ll i = l; i <= r; i++) a[i] += c;
    rebuild(id[l]);
}

ll calc(ll l, ll r, ll x) {
    ll res = 0;
    for (ll i = l; i <= r; i++) res += (a[i] + tag[id[i]] < x);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        R[id[i]] = i;
        if (!L[id[i]]) L[id[i]] = i;
    }
    for (ll k = 0; k <= id[n]; k++) rebuild(k);
    for (ll t = 1; t <= n; t++) {
        ll op, l, r, c;
        cin >> op >> l >> r >> c;
        ll x = l, y = r;
        if (op == 0) {
            if (id[x] == id[y]) add(x, y, c);
            else {
                add(x, R[id[x]], c);
                for (ll k = id[x] + 1; k < id[y]; k++) tag[k] += c;
                add(L[id[y]], y, c);
            }
            continue;
        }
        ll w = c * c, res;
        if (id[x] == id[y]) res = calc(x, y, w);
        else {
            res = calc(x, R[id[x]], w) + calc(L[id[y]], y, w);
            for (ll k = id[x] + 1; k < id[y]; k++)
                res += lower_bound(v[k].begin(), v[k].end(), w - tag[k]) - v[k].begin();
        }
        cout << res << '\n';
    }
}

ChạyInput5
1 4 2 8 3
1 1 5 2
0 2 4 -2
1 1 4 1
1 2 5 3
1 3 3 0

Output3
1
4
0

Độ phức tạp: mỗi thao tác $O(\sqrt n \log n)$: hai lần dựng lại khối hoặc $\sqrt n$ lần chặt nhị phân.

Ngưỡng

Nhiều bài có một tham số $k$ trong mỗi câu hỏi (bước nhảy, modulo, kích thước tập), và cách giải tốt tùy $k$ lớn hay nhỏ.

• $k > S$: đối tượng liên quan chỉ có cỡ $n / k < n / S$ phần tử, nên duyệt thẳng.
• $k \le S$: chỉ có $S$ giá trị khác nhau, nên tính sẵn một bảng cho từng giá trị, hoặc gom các câu hỏi cùng $k$ lại xử lý một lượt.

Chọn $S = \sqrt n$ thì cả hai phía đều $O(\sqrt n)$ mỗi thao tác, tổng cộng $O(n \sqrt n)$.

Ví dụTổng Theo Số Dư

Đề. Mảng $5 \cdot 10^5$ phần tử ban đầu bằng 0, $q \le 5 \cdot 10^5$ thao tác: cộng $y$ vào $a_x$, hoặc in tổng các $a_i$ với $i \bmod x = y$.

Lời giải. Chia câu hỏi theo modulo $x$ tại ngưỡng $S \approx \sqrt{5 \cdot 10^5} \approx 700$. Modulo nhỏ thì có ít, nên giữ sẵn đáp án cho mọi cặp $(d, r)$ với $d \le S$; modulo lớn thì dãy $y, y + x, \dots$ chỉ có ít số, cộng thẳng.

Bước 1: cộng vào $a_x$. Sửa $a_x$ và $S$ ô của bảng: với mỗi $d \le S$, phần tử $x$ thuộc nhóm dư x % d.

a[x] += y;
for (int d = 1; d <= S; d++) sm[d][x % d] += y;

Bước 2: câu hỏi. $x \le S$ thì đọc thẳng sm[x][y]; $x > S$ thì cộng các $a_i$ với $i = y, y + x, \dots$, không quá $5 \cdot 10^5 / 700 \approx 700$ số.

else if (x <= S) cout << sm[x][y] << '\n';
else {
    ll res = 0;
    for (ll i = y; i <= M; i += x) res += a[i];
    cout << res << '\n';
}

Biến vòng d, x, y khai báo int để phép chia lấy dư là phép 32 bit. Vòng trong chạy $3{,}5 \cdot 10^8$ lần nên chênh lệch lộ rõ:

Dùng long long chậm gấp khoảng 3 lần. Vòng lặp nóng có phép chia lấy dư thì ưu tiên int.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll M = 5e5, S = 700;
ll q, a[M + 5], sm[S + 1][S + 1];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> q;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            a[x] += y;
            for (int d = 1; d <= S; d++) sm[d][x % d] += y;
        } else if (x <= S) cout << sm[x][y] << '\n';
        else {
            ll res = 0;
            for (ll i = y; i <= M; i += x) res += a[i];
            cout << res << '\n';
        }
    }
}

ChạyInput7
1 3 5
1 8 4
1 10 -2
2 5 3
2 4 0
1 8 -1
2 2 0

Output9
4
1

Ước lượng phép tính: mỗi thao tác khoảng $S \approx 700$ phép.

Nhảy khỏi khối

Mỗi ô $i$ chỉ sang một ô $i + a_i$ ở bên phải, và $a_i$ có thể bị sửa. Mô phỏng thẳng một đường nhảy tốn tới $n$ bước. Chia dãy thành khối và với mỗi ô lưu ba thứ: nxt[i] là ô đầu tiên ngoài khối của $i$ mà đường đi từ $i$ tới, cnt[i] là số bước để tới đó, lst[i] là ô cuối cùng trong khối trước khi rời. Chúng tính được từ phải sang trong khối: nếu $i + a_i$ còn trong khối thì kế thừa từ ô đó, ngược lại $i$ tự rời khối sau một bước.

Một câu hỏi đi theo nxt, mỗi bước qua ít nhất một khối, nên tốn $O(n / B)$. Sửa $a_p$ chỉ ảnh hưởng các ô cùng khối từ $p$ về trái, tính lại $O(B)$.

Ví dụNhững Bước Nhảy Thoát Mảng

Đề. $n \le 10^5$ ô, ô $i$ có $a_i \ge 1$, đứng ở $i$ thì nhảy tới $i + a_i$, dừng khi vượt $n$. $m \le 10^5$ thao tác: gán $a_p = x$, hoặc bắt đầu ở $p$ và in ô cuối cùng còn trong mảng cùng tổng số bước nhảy.

Lời giải. Chia ô thành khối dài $\sqrt n$. Với mỗi ô $i$ giữ ba thứ: nxt[i] là ô đầu tiên ngoài khối mà đường nhảy từ $i$ tới, cnt[i] là số bước để tới đó, lst[i] là ô cuối cùng trong khối trên đường đi. Câu hỏi đi theo nxt, mỗi bước qua ít nhất một khối. Gán $a_p$ chỉ ảnh hưởng các ô cùng khối và đứng trước $p$. Với ví dụ, khối dài 2: từ ô 1 đường đi $1 \to 3 \to 4 \to 6 \to 10$ qua ba lần nhảy theo nxt.

Bước 1: tính một ô. Nhảy một bước tới $j = i + a_i$. Ra ngoài khối (hoặc ngoài mảng) thì $i$ rời khối sau 1 bước và ô cuối trong khối là chính $i$. Còn trong khối thì kế thừa từ $j$, cộng thêm 1 bước.

void calc(ll i) {
    ll j = i + a[i];
    if (j > n || id[j] != id[i]) {
        nxt[i] = j;
        cnt[i] = 1;
        lst[i] = i;
    } else {
        nxt[i] = nxt[j];
        cnt[i] = cnt[j] + 1;
        lst[i] = lst[j];
    }
}

Bước 2: dựng và sửa. Dựng ban đầu duyệt $i$ từ $n$ về 1, nên $j > i$ luôn đã tính. Gán $a_p$ thì tính lại từ $p$ về đầu khối, $O(B)$.

for (ll i = n; i >= 1; i--) calc(i);

cin >> a[p];
for (ll i = p; i >= L[id[p]]; i--) calc(i);

Bước 3: câu hỏi. Cộng cnt, nhớ lst của bước cuối để in ô cuối cùng còn trong mảng.

ll steps = 0, last = p;
while (p <= n) {
    steps += cnt[p];
    last = lst[p];
    p = nxt[p];
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5;
ll n, m, B, a[N], id[N], L[N], nxt[N], cnt[N], lst[N];

void calc(ll i) {
    ll j = i + a[i];
    if (j > n || id[j] != id[i]) {
        nxt[i] = j;
        cnt[i] = 1;
        lst[i] = i;
    } else {
        nxt[i] = nxt[j];
        cnt[i] = cnt[j] + 1;
        lst[i] = lst[j];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    B = max(1LL, (ll)sqrt(n));
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / B;
        if (!L[id[i]]) L[id[i]] = i;
    }
    for (ll i = n; i >= 1; i--) calc(i);
    while (m--) {
        ll t, p;
        cin >> t >> p;
        if (t == 0) {
            cin >> a[p];
            for (ll i = p; i >= L[id[p]]; i--) calc(i);
            continue;
        }
        ll steps = 0, last = p;
        while (p <= n) {
            steps += cnt[p];
            last = lst[p];
            p = nxt[p];
        }
        cout << last << ' ' << steps << '\n';
    }
}

ChạyInput6 5
2 3 1 2 1 4
1 1
0 3 4
1 1
1 2
0 6 1

Output6 4
3 2
6 3

Độ phức tạp: gán $O(\sqrt n)$, câu hỏi $O(\sqrt n)$ vì qua tối đa $\sqrt n$ khối.

Đỉnh nặng, đỉnh nhẹ

Mục này dùng vài chữ của chương 3: bậc của một đỉnh là số cạnh nối với nó. Mỗi cạnh góp 1 vào bậc của cả hai đầu, nên tổng mọi bậc là $2m$. Vì vậy đồ thị $m$ cạnh có không quá $2m / S$ đỉnh bậc lớn hơn $S$.

Gọi chúng là đỉnh nặng, còn lại là đỉnh nhẹ. Duyệt hàng xóm của một đỉnh nhẹ tốn không quá $S$. Đỉnh nặng thì ít, có thể giữ cho mỗi đỉnh nặng một bảng hay một bộ đếm riêng. Với $S = \sqrt m$ cả hai phía đều $O(\sqrt m)$.

Một cách dùng gọn: hướng mỗi cạnh từ đầu có bậc nhỏ hơn sang đầu có bậc lớn hơn (bằng nhau thì theo chỉ số). Đồ thị thành không có chu trình, và mỗi đỉnh có không quá $\sqrt{2m}$ cạnh đi ra: một đỉnh có $d$ cạnh đi ra thì cả $d$ hàng xóm đó có bậc ít nhất bằng nó, tức ít nhất $d$, nên $d \cdot d \le 2m$.

Ví dụTam Giác Trong Mạng Lưới

Đề. Đồ thị đơn $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh. Đếm số tam giác.

Lời giải. Hướng mỗi cạnh từ đầu có bậc nhỏ hơn sang đầu bậc lớn hơn (bằng nhau thì theo chỉ số); đồ thị hướng này không có chu trình. Mỗi tam giác có đúng một đỉnh mà cả hai cạnh của tam giác đều đi ra từ nó, nên được đếm đúng một lần ở đỉnh đó. Mỗi đỉnh có không quá $\sqrt{2m}$ cạnh đi ra: đỉnh có $d$ cạnh ra thì mỗi đỉnh nó đi tới có bậc ít nhất $d$, nên $d \cdot d \le 2m$.

Bước 1: đếm bậc rồi hướng cạnh.

for (ll i = 1; i <= m; i++) {
    ll u = eu[i], v = ev[i];
    if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
    g[u].push_back(v);
}

Bước 2: đếm tam giác ở đỉnh có hai cạnh ra. Đánh dấu các đỉnh $u$ đi tới bằng mark[v] = u; dùng chính $u$ làm dấu nên khỏi xóa mảng giữa các lượt. Với mỗi $v$ mà $u$ đi tới, mỗi $w$ mà $v$ đi tới và đã được đánh dấu là một tam giác $(u, v, w)$.

for (ll u = 1; u <= n; u++) {
    for (ll v : g[u]) mark[v] = u;
    for (ll v : g[u])
        for (ll w : g[v])
            if (mark[w] == u) ans++;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, deg[N], eu[M], ev[M], mark[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        deg[eu[i]]++;
        deg[ev[i]]++;
    }
    for (ll i = 1; i <= m; i++) {
        ll u = eu[i], v = ev[i];
        if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
        g[u].push_back(v);
    }
    ll ans = 0;
    for (ll u = 1; u <= n; u++) {
        for (ll v : g[u]) mark[v] = u;
        for (ll v : g[u])
            for (ll w : g[v])
                if (mark[w] == u) ans++;
    }
    cout << ans << '\n';
}

ChạyInput5 6
1 2
2 3
1 3
3 4
4 5
3 5

Output2

Độ phức tạp: mỗi cạnh $u \to v$ tốn số cạnh ra của $v$, không quá $\sqrt{2m}$: tổng $O(m \sqrt m)$, khoảng $10^8$ phép đơn giản.