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$".

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".