Phân rã căn bậc hai (Square Root Decomposition)

tác giả: Ir1d, HeRaNO, Xeonacid

Giới thiệu

Thực ra, chia khối (block decomposition) là một tư tưởng, chứ không phải là một cấu trúc dữ liệu.

Từ NOIP đến NOI đến IOI, tư tưởng chia khối xuất hiện ở các mức độ khó khác nhau.

Tư tưởng cơ bản của chia khối là thông qua việc phân chia hợp lý dữ liệu gốc, và tiền xử lý một phần thông tin trên mỗi khối đã chia, từ đó đạt được độ phức tạp thời gian tốt hơn so với các thuật toán vét cạn thông thường.

Độ phức tạp thời gian của chia khối chủ yếu phụ thuộc vào độ dài khối, thông thường có thể tìm ra độ dài khối tối ưu cho một bài toán nhất định và độ phức tạp thời gian tương ứng bằng cách sử dụng bất đẳng thức trung bình.

Chia khối là một tư tưởng rất linh hoạt, ưu điểm so với mảng Fenwick (BIT) và cây đoạn là tính phổ dụng tốt hơn, có thể duy trì nhiều thông tin mà mảng Fenwick và cây đoạn không thể duy trì.

Tất nhiên, nhược điểm của chia khối là độ phức tạp tiệm cận không tốt bằng cây đoạn và mảng Fenwick.

Tuy nhiên, trong hầu hết các bài toán, chia khối vẫn là một lựa chọn tốt để giải quyết các bài toán này.

Dưới đây là một vài ví dụ.

Tổng đoạn

Bài toán LibreOJ 6280 Nhập môn Chia khối Dãy số 4

Cho một dãy \(\{a_i\}\) có độ dài \(n\), cần thực hiện \(n\) thao tác. Thao tác chia làm hai loại:

Cộng \(x\) vào tất cả các số từ \(a_l\) đến \(a_r\);
Tính \(\sum_{i=l}^r a_i\).

\(1 \leq n \leq 5 \times 10^4\)

Chúng ta chia dãy thành các khối, mỗi khối có \(s\) phần tử, và ghi lại tổng đoạn của mỗi khối là \(b_i\).

\[ \underbrace{a_1, a_2, \ldots, a_s}_{b_1}, \underbrace{a_{s+1}, \ldots, a_{2s}}_{b_2}, \dots, \underbrace{a_{(s-1) \times s+1}, \dots, a_n}_{b_{\frac{n}{s}}} \]

Khối cuối cùng có thể không đầy đủ (vì \(n\) rất có thể không phải là bội số của \(s\)), nhưng điều này không ảnh hưởng lớn đến thảo luận của chúng ta.

Trước tiên xem xét thao tác truy vấn:

Nếu \(l\) và \(r\) nằm trong cùng một khối, trực tiếp tính tổng vét cạn, vì độ dài khối là \(s\), nên độ phức tạp xấu nhất là \(O(s)\).
Nếu \(l\) và \(r\) không nằm trong cùng một khối, thì kết quả được tạo thành từ ba phần: khối không đầy đủ bắt đầu từ \(l\), các khối đầy đủ ở giữa, và khối không đầy đủ kết thúc tại \(r\). Đối với các khối không đầy đủ, vẫn sử dụng phương pháp tính vét cạn ở trên; đối với các khối đầy đủ, trực tiếp sử dụng \(b_i\) đã tính để tính tổng. Trong trường hợp này, độ phức tạp xấu nhất là \(O(\dfrac{n}{s}+s)\).

Tiếp theo là thao tác sửa đổi:

Nếu \(l\) và \(r\) nằm trong cùng một khối, trực tiếp sửa đổi vét cạn, vì độ dài khối là \(s\), nên độ phức tạp xấu nhất là \(O(s)\).
Nếu \(l\) và \(r\) không nằm trong cùng một khối, cần sửa đổi ba phần: khối không đầy đủ bắt đầu từ \(l\), các khối đầy đủ ở giữa, và khối không đầy đủ kết thúc tại \(r\). Đối với các khối không đầy đủ, vẫn là sửa đổi vét cạn giá trị của từng phần tử (đừng quên cập nhật tổng đoạn \(b_i\)), đối với các khối đầy đủ, trực tiếp sửa đổi \(b_i\). Trong trường hợp này, độ phức tạp xấu nhất vẫn là \(O(\dfrac{n}{s}+s)\).

Theo bất đẳng thức trung bình, khi \(\dfrac{n}{s}=s\), tức là \(s=\sqrt n\), độ phức tạp thời gian cho mỗi thao tác là tối ưu, là \(O(\sqrt n)\).

Code tham khảo

#include <cmath>
#include <iostream>
using namespace std;
int id[50005], len;
// id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优
long long a[50005], b[50005], s[50005];

// a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s
// 表示块内元素总和
void add(int l, int r, long long x) {  // 区间加法
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // 在一个块中
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++)
    b[i] += x, s[i] += len * x;  // 更新区间和数组(完整的块)
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // 以上两行不完整的块直接简单求和,就OK
}

long long query(int l, int r, long long p) {  // 区间查询
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // 在一个块里直接暴力求和
    for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p;
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p;
  for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p;
  for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p;
  // 和上面的区间修改是一个道理
  return ans;
}

int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // 均值不等式可知复杂度最优为根号n
  for (int i = 1; i <= n; i++) {  // 题面要求
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }
  for (int i = 1; i <= n; i++) {
    int op, l, r, c;
    cin >> op >> l >> r >> c;
    if (op == 0)
      add(l, r, c);
    else
      cout << query(l, r, c + 1) << endl;
  }
  return 0;
}

/*
https://loj.ac/s/1151495
 */

Tổng đoạn 2

Cách tiếp cận trước có độ phức tạp \(\Omega(1), O(\sqrt{n})\).

Ở đây chúng ta giới thiệu một thuật toán \(O(\sqrt{n}) - O(1)\).

Để truy vấn \(O(1)\), chúng ta có thể duy trì các loại tổng tiền tố khác nhau.

Tuy nhiên, khi có sửa đổi, việc duy trì không thuận tiện, chỉ có thể duy trì tổng tiền tố trong phạm vi từng khối.

Và tổng tiền tố của cả khối như một đơn vị.

Mỗi lần sửa đổi là \(O(T+\frac{n}{T})\).

Truy vấn: liên quan đến ba phần, mỗi phần đều có thể nhận được trực tiếp thông qua tổng tiền tố, độ phức tạp thời gian là \(O(1)\).

Chia khối cho truy vấn

Cùng một bài toán, bây giờ độ dài dãy là \(n\), có \(m\) thao tác.

Nếu số lượng thao tác tương đối ít, chúng ta có thể ghi lại các thao tác, và cộng tác động của các thao tác này vào lúc truy vấn.

Giả sử tối đa ghi nhớ \(T\) thao tác, thì sửa đổi \(O(1)\), truy vấn \(O(T)\).

Sau \(T\) thao tác, tính toán lại tổng tiền tố, \(O(n)\).

Độ phức tạp tổng: \(O(mT+n\frac{m}{T})\).

Khi \(T=\sqrt{n}\), độ phức tạp tổng là \(O(m \sqrt{n})\).

Các bài toán khác

Tư tưởng chia khối cũng có thể được áp dụng cho các bài toán liên quan đến số nguyên khác: tìm số lượng phần tử bằng 0, tìm phần tử khác 0 đầu tiên, tính số lượng phần tử thỏa mãn một thuộc tính nào đó, v.v.

Còn có một số bài toán có thể được giải quyết bằng chia khối, ví dụ như duy trì một tập hợp cho phép thêm hoặc xóa các số, kiểm tra xem một số có thuộc tập hợp này hay không, và tìm số lớn thứ \(k\). Để giải quyết bài toán này, cần lưu trữ các số theo thứ tự tăng dần và chia thành nhiều khối, mỗi khối chứa \(\sqrt{n}\) số. Mỗi lần thêm hoặc xóa một số, cần phải phân chia lại khối bằng cách di chuyển các số ở ranh giới giữa các khối liền kề.

Một thuật toán offline nổi tiếng Thuật toán Mo, cũng được thực hiện dựa trên tư tưởng chia khối.

Bài tập thực hành

UVa - 12003 - Array Transformer
UVa - 11990 Dynamic Inversion
SPOJ - Give Away
Codeforces - Till I Collapse
Codeforces - Destiny
Codeforces - Holes
Codeforces - XOR and Favorite Number
Codeforces - Powerful array
SPOJ - DQUERY

Trang này chủ yếu dịch từ bài viết Sqrt-декомпозиция và bản dịch tiếng Anh của nó Sqrt Decomposition. Bản tiếng Nga có giấy phép Public Domain + Leave a Link; bản tiếng Anh có giấy phép CC-BY-SA 4.0.

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply