Sqrt Decomposition

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 8, Tháng 4, 2026, 16:10

Sqrt Decomposition (phân rã căn bậc hai) là kỹ thuật chia mảng thành các block kích thước $\sqrt{N}$ để trả lời truy vấn và cập nhật trong $O (\sqrt{N})$ — đơn giản hơn Segment Tree nhưng đủ mạnh cho nhiều bài.

Ý tưởng cơ bản

Chia mảng $a [0 . . N - 1]$ thành $⌈ N / B ⌉$ block kích thước $B \approx \sqrt{N}$ . Với mỗi block lưu thông tin tổng hợp (tổng, min, max,...).

Truy vấn $[l, r]$ : Xử lý riêng phần thừa ở hai đầu ( $O (B)$ phần tử), và các block hoàn chỉnh ở giữa ( $O (N / B)$ block).

Cài đặt: Range Sum + Point Update

const int MAXN = 1e5 + 5;
int a[MAXN], block_sum[320];   // block[i] = tổng block thứ i
int B;   // kích thước block

void build(int n) {
    B = max(1, (int)sqrt(n));
    for (int i = 0; i < n; i++)
        block_sum[i / B] += a[i];
}

void update(int i, int val) {
    block_sum[i / B] += val - a[i];
    a[i] = val;
}

long long 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];
    } else {
        for (int i = l; i < (bl+1)*B; i++) ans += a[i];
        for (int b = bl+1; b < br; b++) ans += block_sum[b];
        for (int i = br*B; i <= r; i++) ans += a[i];
    }
    return ans;
}

Cài đặt: Range Update + Range Query (lazy)

Dùng lazy tag cho mỗi block:

long long lazy[320];   // lazy[b] = giá trị cộng thêm cho toàn bộ block b

void range_add(int l, int r, long long val, int n) {
    int bl = l / B, br = r / B;
    if (bl == br) {
        for (int i = l; i <= r; i++) a[i] += val;
        block_sum[bl] += val * (r - l + 1);
    } else {
        for (int i = l; i < (bl+1)*B; i++) { a[i] += val; block_sum[bl] += val; }
        for (int b = bl+1; b < br; b++) { lazy[b] += val; block_sum[b] += val * B; }
        for (int i = br*B; i <= r; i++) { a[i] += val; block_sum[br] += val; }
    }
}

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];
        for (int i = br*B; i <= r; i++) ans += a[i] + lazy[br];
    }
    return ans;
}

Ứng dụng: Offline Sort (Chtholly Tree thay thế)

Sqrt decomposition với rebuild block khi block bị thay đổi nhiều:

// Khi cập nhật block không hoàn chỉnh: thay đổi từng phần tử (O(B))
// Khi truy vấn block hoàn chỉnh: dùng thông tin đã tổng hợp (O(1))
// Rebuild: sort lại block sau khi cập nhật nhiều lần (O(B log B))

Ứng dụng: Range Assign + Range Min

Bài toán phức tạp hơn Segment Tree lazy:

int assign_lazy[320];   // -1 = chưa assign
memset(assign_lazy, -1, sizeof(assign_lazy));

void range_assign(int l, int r, int val, int n) {
    int bl = l / B, br = r / B;
    if (bl == br) {
        // Rebuild block bl trước
        for (int i = bl*B; i < min(n, (bl+1)*B); i++)
            if (assign_lazy[bl] != -1) a[i] = assign_lazy[bl];
        assign_lazy[bl] = -1;
        for (int i = l; i <= r; i++) a[i] = val;
        // Tính lại block_sum[bl]
    } else {
        // Xử lý block bl và br (partial) + các block giữa (lazy)
        for (int b = bl+1; b < br; b++) assign_lazy[b] = val;
    }
}

Độ phức tạp

Thao tác	Block size $B$	Độ phức tạp
Point update + Range query	$\sqrt{N}$	$O (\sqrt{N})$
Range update + Point query	$\sqrt{N}$	$O (\sqrt{N})$
Range update + Range query	$\sqrt{N}$	$O (\sqrt{N})$

Khi nào dùng Sqrt Decomposition?

Bài có thao tác phức tạp không thể lazy trên Segment Tree.
Mo's Algorithm (sắp xếp truy vấn theo block).
Giới hạn thời gian rộng ( $N \leq 10^{5}$ , TL $\geq 2$ s).
Cần cài đặt nhanh hơn Segment Tree mà vẫn đủ mạnh.

Bình luận

Không có bình luận tại thời điểm này.