Sqrt Decomposition

Sqrt Decomposition (phân rã căn bậc hai, hay "phân khối") là kỹ thuật chia mảng $a[0..N-1]$ thành các khối (block) liên tiếp kích thước $B\approx \sqrt{N}$, và lưu sẵn thông tin tổng hợp (tổng, min, max, ...) của từng khối. Nhờ đó, một truy vấn đoạn $[l,r]$ hay một cập nhật được trả lời trong $O(\sqrt{N})$ thay vì $O(N)$ ngây thơ — cài đặt đơn giản hơn Segment Tree nhưng vẫn đủ mạnh cho rất nhiều bài toán truy vấn đoạn.

Ý tưởng / Trực giác

Hãy nghĩ về một truy vấn tổng đoạn $[l,r]$. Cách ngây thơ duyệt từng phần tử mất $O(N)$ mỗi truy vấn. Segment Tree giảm còn $O(\log N)$ nhưng phải cài đặt cây đệ quy. Sqrt decomposition là điểm cân bằng ở giữa: trả giá $O(\sqrt{N})$ nhưng đổi lại cài đặt rất ngắn và dễ tổng quát hoá.

Cốt lõi nằm ở một sự đánh đổi tối ưu. Chia mảng thành các khối cỡ $B$, ta có hai loại đối tượng:

• Khối hoàn chỉnh (nằm trọn trong $[l,r]$): có $O(N/B)$ khối, mỗi khối đã có sẵn giá trị tổng hợp nên trả lời tức thời $O(1)$.
• Phần lẻ ở hai đầu (rìa trái và rìa phải): mỗi đầu nằm gọn trong một khối nên có nhiều nhất $O(B)$ phần tử, ta duyệt tay từng phần tử.

Tổng chi phí một truy vấn là $O(N/B+B)$. Đây là tổng của hai đại lượng có tích cố định ($\frac{N}{B}·B=N$), nên theo bất đẳng thức AM-GM nó nhỏ nhất khi $N/B=B$, tức $B=\sqrt{N}$, cho chi phí $O(\sqrt{N})$. Đó chính là lý do con số "căn $N$" xuất hiện: nó cân bằng hoàn hảo giữa "số khối phải gộp" và "số phần tử lẻ phải duyệt".

Vì sao đúng? Đoạn $[l,r]$ luôn phân tách duy nhất thành: một mẩu lẻ đầu + một dãy khối hoàn chỉnh ở giữa + một mẩu lẻ cuối. Phép gộp (tổng, min, ...) chỉ cần có tính kết hợp (associative) là ta được phép cộng dồn các mảnh này theo bất kỳ thứ tự nào mà kết quả không đổi. Tổng, XOR, min, max, gcd đều thoả mãn.

Ví dụ chạy tay

Xét mảng $N=9$, chọn $B=3$ (vì $\sqrt{9}=3$), bài toán tổng đoạn:

 chỉ số:   0   1   2 | 3   4   5 | 6   7   8
 a[]:      3   2   4 | 5   1   1 | 5   3   2
            khối 0    |   khối 1  |   khối 2
 block_sum:    9      |     7     |     10
            (3+2+4)   |  (5+1+1)  |  (5+3+2)

Truy vấn tổng $[l=1,r=7]$: khối của $l$ là $bl=1/3=0$, khối của $r$ là $br=7/3=2$. Vì $bl\ne br$, ta tách ba phần:

            [l=1...........r=7]
 a[]:    3 [ 2   4 ]( 5   1   1 )[ 5   3 ] 2
            ^^^^^^^   ^^^^^^^^^^^   ^^^^^
           rìa trái   khối GIỮA    rìa phải
           duyệt tay   block_sum    duyệt tay

• Rìa trái: các chỉ số từ $l=1$ đến hết khối 0 (chỉ số 2): $a[1]+a[2]=2+4=6$.
• Khối giữa hoàn chỉnh: chỉ có khối 1, lấy thẳng $block\_sum[1]=7$. (không duyệt phần tử!)
• Rìa phải: từ đầu khối 2 (chỉ số 6) đến $r=7$: $a[6]+a[7]=5+3=8$.

Kết quả $=6+7+8=21$. Kiểm tra lại: $2+4+5+1+1+5+3=21$. Đúng.

Cập nhật điểm $a[4]=10$ (đang là 1): chỉ cần sửa khối chứa nó, $4/3=1$:

 block_sum[1] += (10 - a[4]) = (10 - 1) = +9  →  block_sum[1] = 7 + 9 = 16
 a[4] = 10

 a[]:      3   2   4 | 5  10   1 | 5   3   2
 block_sum:    9      |    16     |     10

Mọi truy vấn sau đó tự động phản ánh thay đổi vì khối 1 đã được cập nhật. Cả cập nhật lẫn truy vấn đều chỉ chạm tới $O(\sqrt{N})$ ô.

Cài đặt

1. Tổng đoạn + Cập nhật điểm (Range Sum + Point Update)

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

const int MAXN = 2e5 + 5;
long long a[MAXN], block_sum[1000];   // block_sum[b] = tổng các phần tử của khối b
int B;                                // kích thước khối

void build(int n) {
    B = max(1, (int)sqrt(n));         // B ~ sqrt(N) cân bằng hai chi phí
    for (int b = 0; b < 1000; b++) block_sum[b] = 0;
    for (int i = 0; i < n; i++)
        block_sum[i / B] += a[i];     // i/B = chỉ số khối chứa phần tử i
}

// gán a[i] = val
void update(int i, long long val) {
    block_sum[i / B] += val - a[i];   // chỉ chỉnh đúng khối chứa i, O(1)
    a[i] = val;
}

// tổng đoạn [l, r]
long long query(int l, int r) {
    long long ans = 0;
    int bl = l / B, br = r / B;
    if (bl == br) {                   // cùng một khối: duyệt thẳng, không có khối giữa
        for (int i = l; i <= r; i++) ans += a[i];
    } else {
        // rìa trái: từ l đến hết khối bl
        for (int i = l; i < (bl + 1) * B; i++) ans += a[i];
        // các khối hoàn chỉnh ở giữa: lấy sẵn tổng khối
        for (int b = bl + 1; b < br; b++) ans += block_sum[b];
        // rìa phải: từ đầu khối br đến r
        for (int i = br * B; i <= r; i++) ans += a[i];
    }
    return ans;
}

2. Cập nhật đoạn + Truy vấn đoạn (lazy theo khối)

Khi cần cộng giá trị lên cả một đoạn, ta gắn một nhãn lười (lazy tag) cho mỗi khối: với khối hoàn chỉnh chỉ cần ghi vào nhãn thay vì sửa từng phần tử.

long long lazy[1000];   // lazy[b] = giá trị cộng thêm ngầm cho mọi phần tử của khối b

// cộng val cho mọi phần tử trong [l, r]
void range_add(int l, int r, long long val) {
    int bl = l / B, br = r / B;
    if (bl == br) {
        for (int i = l; i <= r; i++) a[i] += val;     // sửa tay phần lẻ
        block_sum[bl] += val * (r - l + 1);
    } else {
        for (int i = l; i < (bl + 1) * B; i++) a[i] += val;
        block_sum[bl] += val * ((bl + 1) * B - l);
        for (int b = bl + 1; b < br; b++) {           // khối giữa: chỉ ghi nhãn lười
            lazy[b] += val;
            block_sum[b] += val * (long long)B;
        }
        for (int i = br * B; i <= r; i++) a[i] += val;
        block_sum[br] += val * (r - br * B + 1);
    }
}

// tổng đoạn [l, r], nhớ cộng nhãn lười khi đọc phần tử lẻ
long long range_query(int l, int r) {
    long long ans = 0;
    int bl = l / B, br = r / B;
    if (bl == br) {
        for (int i = l; i <= r; i++) ans += a[i] + lazy[bl];
    } else {
        for (int i = l; i < (bl + 1) * B; i++) ans += a[i] + lazy[bl];
        for (int b = bl + 1; b < br; b++) ans += block_sum[b];  // block_sum đã gồm lazy
        for (int i = br * B; i <= r; i++) ans += a[i] + lazy[br];
    }
    return ans;
}

Lưu ý mấu chốt: với khối hoàn chỉnh ta dồn cập nhật vào lazy[b] (và đồng bộ block_sum[b]), còn khi đọc phần tử lẻ trong khối $bl$/$br$, giá trị thật của nó là a[i] + lazy[khối].

Độ phức tạp

Bộ nhớ: $O(N)$ cho mảng gốc cộng $O(N/B)=O(\sqrt{N})$ cho mảng khối (block_sum, lazy). Tổng vẫn là $O(N)$.

Với $N=2\times {10}^5$ thì $\sqrt{N}\approx 450$, nên $q$ truy vấn tốn cỡ $q\sqrt{N}\approx 2\times {10}^5\times 450\approx 9\times {10}^7$ phép tính — chạy thoải mái trong vài giây.

⚠️ Lỗi thường gặp

• Tràn số (overflow). Với $N,x_i\le {10}^9$ và $N\le 2\times {10}^5$, tổng một đoạn có thể tới $~2\times {10}^{14}$, vượt int. Khai báo block_sum, biến ans và mảng giá trị bằng long long. Đây là lỗi WA kinh điển của bài tổng đoạn.
• Quên trường hợp $bl==br$. Khi $l$ và $r$ nằm cùng một khối thì không có khối hoàn chỉnh ở giữa, vòng for (b = bl+1; b < br; b++) không chạy nhưng hai vòng rìa lại chồng lấn và đếm trùng/sai. Bắt buộc tách riêng nhánh "cùng khối" duyệt thẳng từ $l$ đến $r$.
• Sai biên giữa rìa và khối. Rìa trái phải chạy đến hết khối $bl$, tức i < (bl+1)*B, còn rìa phải bắt đầu từ đầu khối $br$, tức i = br*B. Lẫn lộn (bl+1)*B với bl*B gây bỏ sót hoặc đếm lặp phần tử ngay tại ranh giới khối — bug rất khó thấy vì chỉ sai ở vài chỉ số biên.
• Khối cuối tràn ra ngoài mảng. $N$ thường không chia hết cho $B$ nên khối cuối ngắn hơn. Mọi vòng lặp theo khối phải chặn chỉ số < n (vd min(n, (b+1)*B)), nếu không sẽ đọc/cộng rác ngoài mảng.
• Lazy không đồng bộ với block_sum. Trong biến thể cộng đoạn, khi ghi lazy[b] += val phải đồng thời block_sum[b] += val*B; và khi đọc phần tử lẻ phải cộng lazy[khối]. Quên một trong hai khiến truy vấn lệch đúng bằng phần lazy chưa áp.
• $B=0$ khi $N$ nhỏ. (int)sqrt(n) có thể ra 0 khi $n$ rất bé, gây chia cho 0 ở i / B. Luôn B = max(1, (int)sqrt(n)).

Biến thể / Mở rộng

• Gán đoạn + min đoạn (range assign + range min): dùng nhãn "assign" cho khối hoàn chỉnh; khi chạm phần lẻ phải "đẩy nhãn" (push down) bằng cách áp nhãn xuống từng phần tử rồi xoá nhãn, sau đó xây lại thông tin khối. Đây là điểm sqrt decomposition linh hoạt hơn Segment Tree với những phép gộp khó kết hợp lazy.
• Mo's Algorithm: sắp xếp các truy vấn offline theo (khối của $l$, rồi $r$). Hai con trỏ $l,r$ dịch tổng cộng $O((N+Q)\sqrt{N})$ lần, giải được loại bài "đếm số phần tử phân biệt / tần suất trong đoạn" mà Segment Tree khó xử lý.
• Phân khối trên giá trị (sqrt trên trục giá trị): thay vì chia theo chỉ số, chia miền giá trị thành khối để hỗ trợ truy vấn kiểu "phần tử nhỏ hơn $k$", "phần tử thứ $k$".

Chia căn theo bậc trên đồ thị

Ý tưởng "chia căn" không chỉ dùng cho mảng. Trên đồ thị $n$ đỉnh, $m$ cạnh, ta chọn ngưỡng $S\approx \sqrt{m}$ và chia đỉnh làm hai loại:

• Đỉnh nặng: bậc $>S$. Vì tổng bậc là $2m$ nên có không quá $2m/S=O(\sqrt{m})$ đỉnh nặng.
• Đỉnh nhẹ: bậc $\le S$, duyệt hết hàng xóm của nó chỉ tốn $O(\sqrt{m})$.

Mẫu dùng phổ biến: với đỉnh nhẹ thì làm "thô" (duyệt hết hàng xóm), còn đỉnh nặng thì xử lý riêng vì chúng rất ít. Ví dụ khi cần "cập nhật giá trị một đỉnh, hỏi tổng trên các hàng xóm của một đỉnh": đỉnh nhẹ đẩy phần chênh lệch (giá trị mới trừ giá trị cũ) sang mọi hàng xóm ($\le S$ bước), còn khi truy vấn thì lấy phần đã được đẩy sẵn và kéo thêm từ các hàng xóm nặng ($\le 2m/S$ bước). Mỗi thao tác $O(\sqrt{m})$.

⚠️ Với phép max thì cách đẩy chỉ đúng khi giá trị mỗi đỉnh chỉ tăng (ví dụ mảng "kết quả tốt nhất" trong QHĐ): đẩy $max$ mới lên hàng xóm luôn an toàn. Nếu giá trị có thể giảm thì không gỡ được giá trị cũ đã đẩy vào max của hàng xóm, phải đổi cấu trúc (ví dụ mỗi đỉnh giữ một multiset hoặc heap có xoá).

Liệt kê tam giác trong $O(m\sqrt{m})$

Duyệt thẳng "với mỗi đỉnh, xét mọi cặp hàng xóm" tốn $\sum \mathrm{deg}(v{)}^2$, có thể lên $O(nm)$ (đồ thị hình sao). Mẹo là định hướng cạnh:

1. Xếp hạng đỉnh theo cặp $(\mathrm{deg}(v),v)$, đảm bảo mọi đỉnh có hạng khác nhau.
2. Mỗi cạnh $\{u,v\}$ được định hướng từ đỉnh hạng thấp sang đỉnh hạng cao. Đồ thị thu được không có chu trình (hạng tăng dần dọc theo cạnh).
3. Mỗi tam giác $\{a,b,c\}$ với hạng $a<b<c$ trở thành đúng ba cung $a\to b$, $b\to c$, $a\to c$. Vậy với mỗi $u$: đánh dấu mọi $w$ thuộc $\mathrm{o}\mathrm{u}\mathrm{t}(u)$, rồi với mỗi $v\in \mathrm{o}\mathrm{u}\mathrm{t}(u)$ và mỗi $w\in \mathrm{o}\mathrm{u}\mathrm{t}(v)$, nếu $w$ được đánh dấu thì $(u,v,w)$ là một tam giác. Mỗi tam giác được đếm đúng một lần (tại đỉnh hạng thấp nhất).

Vì sao mỗi đỉnh có tối đa $O(\sqrt{m})$ cạnh ra? Giả sử $u$ có $d$ cạnh ra. Mọi đích $v$ của các cạnh này có hạng cao hơn nên $\mathrm{deg}(v)\ge \mathrm{deg}(u)\ge d$. Vậy tổng bậc ít nhất là $d·d$, mà tổng bậc bằng $2m$, suy ra $d\le \sqrt{2m}$. Nói theo ngôn ngữ nặng/nhẹ: đỉnh nhẹ có ít cạnh ra vì bậc đã nhỏ; đỉnh nặng chỉ trỏ sang đỉnh nặng khác, mà chỉ có $O(\sqrt{m})$ đỉnh nặng.

Chi phí: vòng trong chạy ${\sum }_{u\to v}|\mathrm{o}\mathrm{u}\mathrm{t}(v)|\le m·\sqrt{2m}=O(m\sqrt{m})$. Phần đánh dấu tốn $O(n+m)$. Với $m=2\times {10}^5$ thì $m\sqrt{2m}\approx 1.3\times {10}^8$ trong trường hợp xấu nhất, còn thực tế thường nhanh hơn nhiều.

Ví dụ chạy tay. Đồ thị 5 đỉnh, cạnh 1-2, 1-3, 2-3, 2-4, 3-4, 3-5, 4-5:

bac:    deg1=2  deg2=3  deg3=4  deg4=3  deg5=2
hang (deg, id) tang dan:  1 < 5 < 2 < 4 < 3

cung da dinh huong        out(u)
  1->2  1->3              out(1) = {2, 3}
  2->3  2->4              out(2) = {3, 4}
  4->3                    out(4) = {3}
  5->3  5->4              out(5) = {3, 4}
                          out(3) = {}

u=1: danh dau {2,3}; v=2: w=3 co dau -> tam giac (1,2,3); w=4 khong
u=2: danh dau {3,4}; v=4: w=3 co dau -> tam giac (2,4,3)
u=4: danh dau {3};   v=3: out rong
u=5: danh dau {3,4}; v=4: w=3 co dau -> tam giac (5,4,3)
Tong: 3 tam giac

Để ý đỉnh 3 bậc lớn nhất có 0 cạnh ra, nên dù nó kề 4 đỉnh, ta không bao giờ duyệt cặp hàng xóm của nó.

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

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> eu(m), ev(m), deg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &eu[i], &ev[i]);
        deg[eu[i]]++; deg[ev[i]]++;
    }
    // rank by (degree, index): orient every edge from lower rank to higher rank
    auto lower = [&](int a, int b) {
        return deg[a] < deg[b] || (deg[a] == deg[b] && a < b);
    };
    vector<vector<int>> out(n + 1);
    for (int i = 0; i < m; i++) {
        int a = eu[i], b = ev[i];
        if (lower(a, b)) out[a].push_back(b);
        else out[b].push_back(a);
    }
    vector<int> mark(n + 1, 0);
    long long triangles = 0;
    for (int u = 1; u <= n; u++) {
        for (int v : out[u]) mark[v] = u;          // tag out-neighbours of u
        for (int v : out[u])
            for (int w : out[v])
                if (mark[w] == u) triangles++;     // u->v, v->w, u->w
    }
    printf("%lld\n", triangles);
    return 0;
}

Code giả sử đồ thị đơn (không khuyên, không cạnh lặp); nếu đề có cạnh lặp thì phải loại trùng trước. Mảng mark ghi số hiệu $u$ làm "dấu thời gian" nên không cần xoá sau mỗi lượt. Đoạn code đã được đối chiếu với brute force $O(n^3)$ trên 1000 đồ thị ngẫu nhiên. Muốn liệt kê thay vì đếm, chỉ cần in bộ $(u,v,w)$ tại chỗ triangles++.

Ứng dụng: đếm và tìm chu trình ngắn

• Chu trình độ dài 4. Mỗi chu trình $a-b-c-d$ có đúng một đỉnh hạng cao nhất $u$. Với mỗi $u$, duyệt các đường $u-v-w$ mà cả $v$ và $w$ đều có hạng thấp hơn $u$, đếm số lần tới mỗi $w$ bằng mảng cnt. Hai đường khác nhau tới cùng $w$ cho một chu trình; tổng số chu trình là ${\sum }_w\left(\genfrac{}{}{0ex}{}{\mathrm{c}\mathrm{n}\mathrm{t}[w]}{2}\right)$ (cộng dồn qua mọi $u$). Sau mỗi $u$ phải đưa cnt về 0, nhưng chỉ ở các $w$ đã chạm (lưu danh sách các $w$ đó, hoặc dùng dấu thời gian như mảng mark ở trên), không được xoá cả mảng. Chi phí: mỗi cạnh $u-v$ với $v$ hạng thấp hơn tốn $\mathrm{deg}(v)$ bước, mà $\mathrm{deg}(v)\le \mathrm{deg}(u)$ nên đó là $min(\mathrm{deg}u,\mathrm{deg}v)$; tổng ${\sum }_{\{u,v\}}min(\mathrm{deg}u,\mathrm{deg}v)=O(m\sqrt{m})$ (tính mỗi cạnh vào đầu mút hạng thấp $v$: tổng bằng ${\sum }_v\mathrm{deg}(v)·|\mathrm{o}\mathrm{u}\mathrm{t}(v)|\le \sqrt{2m}·2m$ nhờ bổ đề số cạnh ra ở trên). Nếu chỉ cần tìm một chu trình thì dừng ngay lần thứ hai chạm $w$.
• Truy vấn "hai đỉnh $a,b$ có kề nhau không" hàng loạt: cạnh $\{a,b\}$ (nếu có) nằm trong $\mathrm{o}\mathrm{u}\mathrm{t}$ của đầu mút hạng thấp hơn, nên chỉ cần quét $\mathrm{o}\mathrm{u}\mathrm{t}$ của đỉnh đó, cỡ $O(\sqrt{m})$ mỗi truy vấn (hoặc sắp xếp $\mathrm{o}\mathrm{u}\mathrm{t}$ rồi chặt nhị phân).
• Đẩy/kéo nặng nhẹ như đã mô tả ở đầu mục: cập nhật giá trị một đỉnh và hỏi tổng (hoặc max, nếu giá trị chỉ tăng) trên hàng xóm, mỗi thao tác $O(\sqrt{m})$.

⚠️ Lưu ý: phải so sánh theo cặp $(\mathrm{deg},\text{chỉ số})$ chứ không chỉ theo bậc. Nếu chỉ dùng bậc, hai đỉnh cùng bậc không biết định hướng cạnh ra sao; định hướng tuỳ tiện có thể sinh chu trình có hướng và làm đếm lặp hoặc sót tam giác.

Bài tập luyện

• Truy Vấn XOR Đoạn (rxorquery) — (Trung cấp) Tổng-XOR đoạn tĩnh: bài nhập môn để luyện đúng khung "rìa lẻ + khối giữa" với phép gộp kết hợp.
• Truy Vấn Tổng Đoạn Động (dynrsum) — (Trung cấp) Tổng đoạn + cập nhật điểm: bài kinh điển nhất của sqrt decomposition, cũng để rèn phản xạ dùng long long.
• Truy Vấn Nhỏ Nhất Đoạn Động (dynrmin) — (Trung cấp) Đổi phép gộp từ tổng sang min: luyện cách lưu min từng khối và xử lý cập nhật điểm khi giá trị tăng/giảm.
• Nhóm Bạn Bò (cowdep) — (Kỳ cựu) Kết hợp phân khối với hai con trỏ / chặt nhị phân, tập áp dụng sqrt decomposition vào bài tổ hợp không hiển nhiên.
• Truy Vấn Bầu Cử (electqry) — (Kỳ cựu) Cập nhật giá trị rồi truy vấn cực trị toàn cục: minh hoạ phân khối trên trục tần suất/giá trị, vượt khả năng lazy của Segment Tree.
• Đồ thị nhiều màu (colgraph) — (Chuyên gia) Phân khối kết hợp DSU trên đồ thị: bài nâng cao cho thấy sức mạnh tổng quát của ý tưởng "chia thành $\sqrt{N}$ phần".

Đề VOI

• Hành trình du lịch (voi12_travel) (Kỳ cựu) VOI 2012: tìm chu trình độ dài 4, xem mục chia căn theo bậc (đề cũng qua được bằng cách khác không cần chia căn).
• Phần thưởng (voi21_bonus) (Kỳ cựu) VOI 2021: một phần của bài là QHĐ cần max trên các giá trị kề trong đồ thị cặp số; dùng đẩy/kéo theo đỉnh nặng, nhẹ (kết hợp thêm trie cho phần nhãn).