Sqrt Tree (truy vấn đoạn O(1))
Sqrt Tree trả lời truy vấn đoạn cho mọi phép kết hợp (tích ma trận, tích modulo, top-2...) trong O(1) sau O(n log log n) tiền xử lý, không cần idempotent như Sparse Table.
Sqrt Tree là cấu trúc dữ liệu trả lời truy vấn đoạn trên mảng tĩnh trong mỗi truy vấn, với phép chỉ cần kết hợp (associative): tổng, tích modulo, nhân ma trận, hợp hàm, ghép xâu, "hai giá trị lớn nhất"... Tiền xử lý tốn thời gian và bộ nhớ. So với cách ngây thơ mỗi truy vấn, Segment Tree mỗi truy vấn, hay Sparse Table nhưng chỉ với phép idempotent, Sqrt Tree vừa nhanh vừa tổng quát.
Bảng so sánh nhanh (mảng tĩnh, phần tử, phép kết hợp ):
| Cấu trúc | Tiền xử lý | Truy vấn | Điều kiện trên |
|---|---|---|---|
| Sparse Table | kết hợp và idempotent (, , , AND, OR) | ||
| Disjoint Sparse Table | chỉ cần kết hợp | ||
| Segment Tree | chỉ cần kết hợp (có cập nhật) | ||
| Chia căn hai tầng | chỉ cần kết hợp | ||
| Sqrt Tree | chỉ cần kết hợp |
Ý tưởng / Trực giác
Bước 1: chia căn, nhưng trả lời bằng ba mảnh
Chia mảng thành các khối liên tiếp dài khoảng . Với mỗi khối, tính sẵn:
- : tích (theo ) từ đầu khối chứa đến ;
- : tích từ đến cuối khối chứa ;
- : tích của trọn các khối .
Có khoảng khối nên bảng có ô, mỗi ô tính từ ô bên trái: .
Nếu và nằm ở hai khối khác nhau thì đoạn tách đúng thành ba mảnh không chồng nhau, theo đúng thứ tự từ trái sang phải:
(mảnh giữa bỏ qua nếu ). Vì ba mảnh rời nhau, không phần tử nào bị tính hai lần, nên không cần idempotent; vì giữ đúng thứ tự trái sang phải, không cần giao hoán. Chỉ cần kết hợp để được phép "đặt ngoặc" tùy ý.
Bước 2: còn trường hợp cùng khối thì sao?
Đây là chỗ chia căn thường phải quét tay . Sqrt Tree xử lý bằng đệ quy: mỗi khối dài lại được xây một tầng y hệt (chia thành khối con dài , có pref/suf/between riêng), rồi khối con lại xây tiếp, ... Độ dài khối giảm theo , nên sau tầng khối chỉ còn dài .
Một truy vấn chỉ cần dùng đúng một tầng: tầng đầu tiên (từ trên xuống) mà và nằm cùng một khối nhưng khác khối con. Ở tầng đó công thức ba mảnh ở trên cho đáp án ngay.
Bước 3: tìm tầng đúng trong bằng bit cao nhất khác nhau
Nếu cứ đi từ tầng trên xuống để tìm tầng phù hợp thì mất . Mẹo: làm tròn lên lũy thừa của 2, , và chọn mọi kích thước khối là lũy thừa của 2. Ở một tầng có khối dài và khối con dài ():
- cùng khối và giống nhau ở mọi bit từ trở lên;
- khác khối con chúng khác nhau ở ít nhất một bit từ trở lên.
Gọi là bit cao nhất mà và khác nhau, tức (một lệnh __builtin_clz). Hai điều kiện trên tương đương với . Các tầng có nên các khoảng phủ kín và rời nhau trên . Ta tính sẵn mảng và tra trong . Riêng nghĩa là , trả về trực tiếp.
Ví dụ chạy tay
Lấy phép là ghép xâu (kết hợp nhưng không giao hoán, không idempotent), mảng chữ cái, chỉ số từ :
array base=0 a b c d e f g h i j k l m n o p ranges 0..3 4..7 8..11 12..15
, nên có hai tầng:
| Tầng | Khối dài | Khối con dài | Dùng khi bit |
|---|---|---|---|
| 0 | |||
| 1 | |||
| (trực tiếp) |
Bảng của tầng 0 (4 khối con abcd | efgh | ijkl | mnop):
j : 0 1 2 3 4 5 6 7 ... 12 13 14 15
pref[j] : a ab abc abcd e ef efg efgh ... m mn mno mnop
suf[j] : abcd bcd cd d efgh fgh gh h ... mnop nop op p
between[x][y] (x <= y):
y=0 y=1 y=2 y=3
x=0 abcd abcdefgh abcdefghijkl abcdefghijklmnop
x=1 efgh efghijkl efghijklmnop
x=2 ijkl ijklmnop
x=3 mnop
Truy vấn . , , , bit cao nhất nên dùng tầng 0. Khối con của là , của là .
array base=0 a b c d e f g h i j k l m n o p highlight orange 1..3 highlight blue 4..11 highlight green 12..13 pointer l 1 pointer r 13 label 2 suf[1] label 7 between[1][2] label 12 pref[13]
Đúng là đoạn , chỉ với 2 phép .
Truy vấn . , , vẫn tầng 0. , kề nhau nên không có mảnh giữa: .
Truy vấn . , : và cùng khối con của tầng 0 (ijkl), nên xuống tầng 1. Ở tầng 1, khối ijkl được chia thành khối con ij | kl:
tầng 1, khối 8..11: j : 8 9 10 11
pref[j]: i ij k kl
suf[j] : ij j kl l
Đáp án .
Truy vấn . , : hai phần tử kề nhau, trả .
Tất cả kết quả trên đã được kiểm tra bằng chương trình bên dưới (thay phép nhân ma trận bằng ghép xâu).
Cài đặt
Phiên bản C++ là Sqrt Tree đầy đủ, viết dạng template nhận phép bất kỳ. Ví dụ dùng tích ma trận modulo : phép này kết hợp nhưng không giao hoán, không idempotent và không có nghịch đảo tổng quát, nên Sparse Table và "tích tiền tố chia ngược" đều bó tay.
Phiên bản Python là bản hai tầng đơn giản (chia căn + pref/suf/between): truy vấn qua nhiều khối , truy vấn nằm gọn trong một khối thì quét . Thường đủ dùng và dễ cài hơn nhiều.
Định dạng vào: dòng đầu ; dòng mỗi dòng 4 số là ma trận ; dòng mỗi dòng (từ ). In ra 4 phần tử của tích .
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1'000'000'007;
// Example non-commutative associative operation: 2x2 matrix product mod p.
struct Mat {
long long a[2][2];
};
Mat mul(const Mat& x, const Mat& y) {
Mat z;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
z.a[i][j] = (x.a[i][0] * y.a[0][j] + x.a[i][1] * y.a[1][j]) % MOD;
return z;
}
// Sqrt tree: O(n log log n) build, O(1) query for any associative op.
template <class T, T (*op)(const T&, const T&)>
struct SqrtTree {
int n, LOG;
vector<T> a;
vector<int> blkBits, subBits; // per layer: block size 2^k, sub-block size 2^s
vector<int> layerOf; // layerOf[h] = layer used when highest differing bit is h
vector<vector<T>> pref, suf, between;
SqrtTree(const vector<T>& v) : n(v.size()) {
LOG = 1;
while ((1 << LOG) < n) LOG++;
int N = 1 << LOG;
a = v;
a.resize(N, v[0]); // padding is never read by a valid query
layerOf.assign(LOG, -1);
for (int k = LOG; k >= 2; k = (k + 1) / 2) {
int s = (k + 1) / 2;
for (int h = s; h < k; h++) layerOf[h] = blkBits.size();
blkBits.push_back(k);
subBits.push_back(s);
}
int L = blkBits.size();
pref.assign(L, vector<T>(N));
suf.assign(L, vector<T>(N));
between.resize(L);
for (int i = 0; i < L; i++) build(i, N);
}
void build(int i, int N) {
int k = blkBits[i], s = subBits[i];
int sub = 1 << s, cnt = 1 << (k - s); // cnt sub-blocks per block
vector<T>& P = pref[i];
vector<T>& S = suf[i];
for (int st = 0; st < N; st += sub) {
P[st] = a[st];
for (int j = st + 1; j < st + sub; j++) P[j] = op(P[j - 1], a[j]);
S[st + sub - 1] = a[st + sub - 1];
for (int j = st + sub - 2; j >= st; j--) S[j] = op(a[j], S[j + 1]);
}
// between[blk*cnt*cnt + x*cnt + y] = op of sub-blocks x..y inside block blk
between[i].resize((size_t)(N >> k) * cnt * cnt);
for (int blk = 0; blk < (N >> k); blk++) {
size_t base = (size_t)blk * cnt * cnt;
int start = blk << k;
for (int x = 0; x < cnt; x++) {
T cur = S[start + (x << s)]; // whole sub-block x = suffix from its first cell
between[i][base + x * cnt + x] = cur;
for (int y = x + 1; y < cnt; y++) {
cur = op(cur, S[start + (y << s)]);
between[i][base + x * cnt + y] = cur;
}
}
}
}
// op(a[l], ..., a[r]), 0-based, l <= r
T query(int l, int r) const {
if (l == r) return a[l];
int h = 31 - __builtin_clz(l ^ r);
if (h == 0) return op(a[l], a[r]); // r == l + 1
int i = layerOf[h];
int k = blkBits[i], s = subBits[i], cnt = 1 << (k - s);
int bl = (l >> s) & (cnt - 1), br = (r >> s) & (cnt - 1);
T res = suf[i][l];
if (bl + 1 < br) {
size_t base = (size_t)(l >> k) * cnt * cnt;
res = op(res, between[i][base + (bl + 1) * cnt + (br - 1)]);
}
return op(res, pref[i][r]);
}
};
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<Mat> v(n);
for (auto& m : v) scanf("%lld %lld %lld %lld", &m.a[0][0], &m.a[0][1], &m.a[1][0], &m.a[1][1]);
SqrtTree<Mat, mul> st(v);
while (q--) {
int l, r;
scanf("%d %d", &l, &r); // 1-based
Mat m = st.query(l - 1, r - 1);
printf("%lld %lld %lld %lld\n", m.a[0][0], m.a[0][1], m.a[1][0], m.a[1][1]);
}
}
import sys
from math import isqrt
MOD = 10**9 + 7
def mul(x, y):
# 2x2 matrix product mod p, matrices stored as tuples (a, b, c, d)
a, b, c, d = x
e, f, g, h = y
return ((a * e + b * g) % MOD, (a * f + b * h) % MOD,
(c * e + d * g) % MOD, (c * f + d * h) % MOD)
class TwoLevelSqrt:
"""Two-level version: O(n) build, O(1) query across blocks,
O(sqrt n) query when l and r fall in the same block."""
def __init__(self, a, op):
self.a, self.op = a, op
n = len(a)
self.b = b = max(1, isqrt(n)) # block size
self.nb = nb = (n + b - 1) // b # number of blocks
self.pref = [None] * n
self.suf = [None] * n
whole = []
for s in range(0, n, b):
e = min(n, s + b)
cur = a[s]
self.pref[s] = cur
for j in range(s + 1, e):
cur = op(cur, a[j])
self.pref[j] = cur
cur = a[e - 1]
self.suf[e - 1] = cur
for j in range(e - 2, s - 1, -1):
cur = op(a[j], cur)
self.suf[j] = cur
whole.append(self.suf[s])
# between[x][y] = op of whole blocks x..y
self.between = [[None] * nb for _ in range(nb)]
for x in range(nb):
cur = whole[x]
self.between[x][x] = cur
for y in range(x + 1, nb):
cur = op(cur, whole[y])
self.between[x][y] = cur
def query(self, l, r): # 0-based, inclusive
bl, br = l // self.b, r // self.b
if bl == br: # same block: scan directly
res = self.a[l]
for j in range(l + 1, r + 1):
res = self.op(res, self.a[j])
return res
res = self.suf[l]
if bl + 1 < br:
res = self.op(res, self.between[bl + 1][br - 1])
return self.op(res, self.pref[r])
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
vals = list(map(int, data[2:2 + 4 * n]))
a = [tuple(vals[4 * i:4 * i + 4]) for i in range(n)]
st = TwoLevelSqrt(a, mul)
out = []
pos = 2 + 4 * n
for _ in range(q):
l, r = int(data[pos]) - 1, int(data[pos + 1]) - 1
pos += 2
out.append(" ".join(map(str, st.query(l, r))))
print("\n".join(out))
if __name__ == "__main__":
main()
Ví dụ chạy (cả hai chương trình cho cùng kết quả):
Input:
5 4
1 1 1 0
2 0 0 1
1 1 0 1
0 1 1 0
3 0 1 1
1 5
2 3
3 4
4 4
Output:
11 2 8 2
2 2 0 1
1 1 1 0
0 1 1 0
Kiểm tra tay truy vấn : . Nếu nhân ngược thứ tự sẽ ra , khác hẳn: đó là lý do phải tính (phần tử mới đứng bên trái).
Cả hai cài đặt đã được đối chiếu với cách nhân trực tiếp trên hàng nghìn mảng ngẫu nhiên (, mọi cặp ), với cả phép nhân ma trận lẫn phép ghép xâu. Bản C++ dựng với ma trận và trả lời truy vấn trong khoảng giây.
Độ phức tạp
- Số tầng. Số mũ khối giảm , bắt đầu từ và dừng khi , nên có tầng. Với (): các tầng có , tức chỉ 5 tầng.
- Tiền xử lý mỗi tầng . và : mỗi ô một phép , tổng . : mỗi khối dài có khối con, bảng ô, cộng trên khối được ô, mỗi ô một phép .
- Tổng tiền xử lý: thời gian và bộ nhớ ().
- Truy vấn : một
__builtin_clz, một lần tra , vài phép dịch bit và tối đa 2 phép . Không có vòng lặp nào. - Bản Python hai tầng: dựng (bảng có ô), truy vấn khi khác khối và khi cùng khối.
Nếu bản thân phép tốn (vd nhân ma trận tốn ), nhân mọi con số trên với , và bộ nhớ nhân với kích thước một phần tử.
⚠️ Lỗi thường gặp
- Đảo thứ tự với phép không giao hoán. Viết
S[j] = op(S[j+1], a[j])hoặc ghép ba mảnh theo thứ tựpref, between, sufcho kết quả sai với nhân ma trận, ghép xâu, hợp hàm, nhưng vẫn đúng với tổng hay tích số, nên test bằng tổng không phát hiện được. Cách tránh: luôn giữ thứ tự trái sang phải, và test với một phép không giao hoán như ghép xâu. - Dùng mẹo hai đoạn chồng nhau của Sparse Table. Với phép không idempotent (tổng, tích, top-2, ma trận), phần chồng bị tính hai lần. Triệu chứng: tổng bị cộng đôi, "hai số lớn nhất" ra cùng một phần tử hai lần. Đó chính là lý do cần Sqrt Tree hoặc Disjoint Sparse Table.
- Tưởng tích tiền tố + nghịch đảo là đủ. chỉ đúng khi mọi phần tử khả nghịch: hỏng khi có , khi modulo không nguyên tố, khi ma trận suy biến, hay với phép như của tổng. Sqrt Tree không cần nghịch đảo.
- Quên trường hợp và . Ở tầng cuối , , nên không có tầng nào ( trong code). Bỏ hai dòng
ifđầuquerysẽ đọclayerOf[0] = -1và truy cập ngoài mảng; còn thì__builtin_clz(0)là hành vi không xác định. - Không làm tròn lên lũy thừa của 2. Mẹo "bit cao nhất khác nhau" chỉ đúng khi mọi khối bắt đầu ở bội của kích thước khối và kích thước là lũy thừa của 2. Giá trị độn thêm ở cuối (code dùng ) không bao giờ được đọc với truy vấn , vì mọi mảnh dùng đến đều nằm trong .
- Bộ nhớ với phần tử lớn. Mỗi tầng giữ ô pref/suf và tối đa ô between: với (, 5 tầng) code trên giữ khoảng phần tử. Với ma trận kiểu
long long(32 byte) là khoảng 110 MB; nếu giới hạn chặt, lưu phần tử bằngint(giá trị ) và chỉ éplong longkhi nhân, hoặc dùng bản hai tầng. - Tràn số khi nhân modulo. với là khoảng , vẫn vừa
long long(tối đa ), nhưng cộng thêm hạng tử thứ ba (ma trận ) mà không lấy modulo giữa chừng thì có thể tràn.
Biến thể / Mở rộng
- Disjoint Sparse Table. Cùng ý tưởng "suf của nửa trái pref của nửa phải", nhưng chia đôi đệ quy thay vì chia căn: ở mức , mảng chia thành khối dài , mỗi khối lưu suffix của nửa trái và prefix của nửa phải. Truy vấn chọn mức theo bit cao nhất của , ghép đúng 2 mảnh. Cài ngắn hơn Sqrt Tree nhưng tốn bộ nhớ thay vì . Trên thực tế với hai con số khá gần nhau (khoảng ô so với khoảng ô của cài đặt trên), nên Disjoint Sparse Table thường là lựa chọn gọn hơn khi bộ nhớ không quá chặt.
- Cập nhật điểm. Gán thì ở mỗi tầng chỉ khối con chứa phải tính lại , nhưng bảng ở tầng trên cùng có ô bị ảnh hưởng. Kỹ thuật chuẩn (xem cp-algorithms) thay bảng tầng trên cùng bằng một Sqrt Tree nhỏ dựng trên giá trị "trọn khối", đưa cập nhật điểm về mà truy vấn vẫn . Nếu cập nhật nhiều, Segment Tree cho cả hai thao tác thường là lựa chọn hợp lý hơn.
- Khi nào thực sự cần. Với , Segment Tree hay bản chia căn hai tầng thường đã đủ nhanh. Sqrt Tree đáng giá khi rất lớn (cỡ đến truy vấn trực tuyến) trên mảng tĩnh, hoặc khi phép đắt (ma trận) nên muốn số phép mỗi truy vấn là hằng số.
- Phép thường gặp. Tích ma trận (đếm đường đi, quy hoạch động tuyến tính trên đoạn, xem Lũy thừa ma trận), hợp các hàm tuyến tính , "hai giá trị lớn nhất theo vị trí", tổng đoạn con lớn nhất (lưu bộ 4 giá trị: tổng, max tiền tố, max hậu tố, max đoạn con).
- Truy vấn offline. Nếu được đọc trước mọi truy vấn, chia để trị (gom truy vấn đi qua điểm giữa) cũng cho với bộ nhớ; xem thêm Thuật toán Mo cho các truy vấn không có phép kết hợp đẹp.
Bài tập luyện
Kho bài CTOJ hiện chưa có bài nào bắt buộc phải dùng Sqrt Tree (giới hạn thường đủ rộng cho Sparse Table hoặc Segment Tree). Các bài dưới đây là truy vấn đoạn tĩnh, giải được trọn vẹn bằng Sqrt Tree; hai bài sau dùng phép gộp không idempotent, đúng chỗ mạnh của cấu trúc này.
- RMQ tĩnh, min đoạn (rmqspar) (Dễ) Bài khởi động: thay
mulbằngminđể kiểm tra cài đặt Sqrt Tree trên , rồi so với Sparse Table. - Điền phiếu (dhbb25dx2811_dienphieu) (Trung bình) Max đoạn với truy vấn trên mảng tĩnh; luyện đọc nhanh và trả lời mỗi truy vấn.
- Dữ liệu (dhbb23_rdat) (Trung bình) Đáp án quy về tổng hai giá trị lớn nhất theo vị trí trong đoạn; phép gộp "top-2" không idempotent, nên dùng hai đoạn chồng nhau sẽ đếm một phần tử hai lần, còn ba mảnh rời nhau của Sqrt Tree thì không.
- Mã hóa (dhbb25dx4310_mahoa) (Trung bình) Tích lớn nhất của hai phần tử trong đoạn, quy về hai số lớn nhất và hai số nhỏ nhất; phần tử của cấu trúc là một bộ 4 giá trị với phép gộp kết hợp nhưng không idempotent.
Bình luận