Phân khối là kỹ thuật hiệu quả để giải quyết các bài toán thao tác trên dãy số, đặc biệt với truy vấn khoảng. Phương pháp chia dãy thành các khối có kích thước gần bằng nhau, mỗi khối lưu trữ thông tin tổng hợp. Khi xử lý truy vấn, phần biên được duyệt trực tiếp, phần giữa sử dụng thông tin đã xử lý sẵn, đạt độ phức tạp O(√n).

Cấu trúc cơ bản

• Xác định kích thước khối: block_size = (int)sqrt(n);
• Tìm khối cho vị trí i: block_idx[i] = (i - 1) / block_size + 1;
• Ranh giới khối: start_block[b] = (b - 1) * block_size + 1;, end_block[b] = min(start_block[b] + block_size - 1, n);
• Tổng số khối: total_blocks = (n + block_size - 1) / block_size;

Thao tác cập nhật khoảng

void update_range(int l, int r, int value) {
    if (block_idx[l] == block_idx[r]) {
        for (int i = l; i <= r; i++) {
            data[i] += value;
            block_sum[block_idx[i]] += value;
        }
        return;
    }
    // Xử lý khối đầu
    for (int i = l; i <= end_block[block_idx[l]]; i++) {
        data[i] += value;
        block_sum[block_idx[i]] += value;
    }
    // Xử lý khối cuối
    for (int i = start_block[block_idx[r]]; i <= r; i++) {
        data[i] += value;
        block_sum[block_idx[i]] += value;
    }
    // Xử lý khối giữa
    for (int b = block_idx[l] + 1; b < block_idx[r]; b++) {
        lazy[b] += value;
        block_sum[b] += block_size * value;
    }
}

Thao tác truy vấn giá trị nhỏ hơn x

Mỗi khối được sắp xếp để hỗ trợ binary search:

int count_less(int block_id, int threshold) {
    int low = start_block[block_id], high = end_block[block_id];
    int result = low - 1;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (sorted_data[mid] + lazy[block_id] < threshold) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result - start_block[block_id] + 1;
}

int query_range(int l, int r, int threshold) {
    int count = 0;
    if (block_idx[l] == block_idx[r]) {
        for (int i = l; i <= r; i++) {
            if (data[i] + lazy[block_idx[i]] < threshold) count++;
        }
        return count;
    }
    for (int i = l; i <= end_block[block_idx[l]]; i++) {
        if (data[i] + lazy[block_idx[i]] < threshold) count++;
    }
    for (int i = start_block[block_idx[r]]; i <= r; i++) {
        if (data[i] + lazy[block_idx[i]] < threshold) count++;
    }
    for (int b = block_idx[l] + 1; b < block_idx[r]; b++) {
        count += count_less(b, threshold);
    }
    return count;
}

Phân khối giá trị

Khi thao tác liên quan đến giá trị, chia trục giá trị thành các đoạn. Ví dụ bài toán tìm phần tử phổ biến nhất trong khoảng: sử dụng mảng cnt[block][value] để đếm tần suất, kết hợp binary search trên giá trị để tối ưu.

Lưu ý quan trọng

• Xử lý trường hợp đặc biệt khi khoảng nằm trong một khối
• Khi tính end_block phải dùng min() để tránh vượt giới hạn
• Phân biệt rõ chỉ số khối và chỉ số phần tử trong dãy
• Tránh memset toàn bộ mảng, dùng stack để quản lý bộ nhớ tạm