Chtholly Tree (Old Driver Tree)
Lưu mảng thành các khối liên tiếp cùng giá trị trong một cây cân bằng; phép gán đoạn gộp mọi khối thành một, các thao tác khác duyệt từng khối. Hiệu quả bảo đảm khi chỉ có phép gán, và khi dữ liệu ngẫu nhiên.
Chtholly tree (còn gọi là Old Driver Tree, viết tắt ODT, hay "cây gán đoạn") là cách lưu một mảng dưới dạng danh sách các khối liên tiếp có cùng giá trị, đặt trong một cây cân bằng (std::map hoặc std::set) theo vị trí bắt đầu khối. Phép gán cả đoạn xóa mọi khối nằm trong và thay bằng đúng một khối, nên số khối luôn được "dọn" lại. Các thao tác khác (cộng đoạn, tìm phần tử nhỏ thứ , tổng lũy thừa...) chỉ cần duyệt từng khối trong đoạn.
Tên gọi đến từ bài Codeforces 896C (Willem, Chtholly and Seniorious), nơi kỹ thuật này được phổ biến. Nó không phải cấu trúc có độ phức tạp bảo đảm cho mọi thao tác: chỉ hiệu quả khi đề có nhiều phép gán đoạn (dữ liệu ngẫu nhiên, hoặc phép gán là thao tác cập nhật duy nhất). Đổi lại, code rất ngắn và làm được những truy vấn mà segment tree khó làm (ví dụ với thay đổi, hay các đại lượng phụ thuộc vào độ dài khối).
Ý tưởng / Trực giác
Biểu diễn. Lưu odt[p] = v nghĩa là có một khối bắt đầu tại mang giá trị , kéo dài tới ngay trước khối kế tiếp. Thêm một khối cầm canh tại để mọi khối thật đều có "khối kế tiếp", nhờ đó độ dài khối luôn tính được bằng hiệu hai vị trí bắt đầu.
Thao tác nền tảng: split(p). Bảo đảm có một khối bắt đầu đúng tại : tìm khối đang chứa ; nếu thì xong, ngược lại cắt nó thành và (cùng giá trị). Sau split(l) và split(r + 1), đoạn là hợp của một dãy khối liên tiếp trong cây, và mọi thao tác chỉ việc duyệt dãy khối đó.
Gán đoạn làm giảm số khối. assign(l, r, x) gọi hai lần split (tăng số khối thêm tối đa 2), rồi xóa toàn bộ khối trong và chèn một khối. Mỗi khối bị xóa tối đa một lần sau khi được tạo, nên nếu chỉ có phép gán (và truy vấn chỉ duyệt các khối sắp bị xóa), tổng số khối được tạo ra là và tổng chi phí là khấu hao.
Khi có thêm thao tác duyệt khối (cộng đoạn, truy vấn). Chi phí một thao tác bằng số khối trong đoạn. Nếu các thao tác được sinh ngẫu nhiên (như bài gốc), khoảng số thao tác là phép gán với đoạn ngẫu nhiên, nên số khối nhanh chóng giảm xuống rất nhỏ; các phân tích phổ biến ước lượng tổng chi phí kỳ vọng chỉ cỡ lần duyệt khối. Nhưng với dữ liệu cố ý xấu (ví dụ gán từng điểm xen kẽ hai giá trị rồi hỏi cả mảng nhiều lần), mỗi truy vấn phải duyệt khối và tổng thành .
Nói ngắn gọn: hãy dùng Chtholly tree khi mọi thao tác duyệt khối đều kèm theo việc xóa các khối đó (phép gán đoạn, sắp xếp đoạn...), hoặc khi đề nói rõ dữ liệu ngẫu nhiên. Khi truy vấn chỉ đọc mà không xóa, phải tự hỏi số khối có thể lớn tới đâu.
Ví dụ chạy tay
Mảng ban đầu , mỗi phần tử là một khối (ký hiệu ):
[1,1]=3 [2,2]=1 [3,3]=4 [4,4]=1 [5,5]=5 [6,6]=9 (+ cầm canh tại 7)
1. Gán : split(1) và split(7) không tạo khối mới. Xóa cả 6 khối, chèn một khối:
[1,6]=4
2. Gán : split(3) cắt thành và ; split(5) cắt thành và . Xóa , chèn khối mới:
sau split(3): [1,2]=4 [3,6]=4
sau split(5): [1,2]=4 [3,4]=4 [5,6]=4
sau gán: [1,2]=4 [3,4]=9 [5,6]=4
3. Cộng vào : split(2) cắt , split(6) cắt , rồi cộng vào ba khối nằm giữa:
sau split(2): [1,1]=4 [2,2]=4 [3,4]=9 [5,6]=4
sau split(6): [1,1]=4 [2,2]=4 [3,4]=9 [5,5]=4 [6,6]=4
sau cộng: [1,1]=4 [2,2]=5 [3,4]=10 [5,5]=5 [6,6]=4
Mảng thật lúc này là .
4. Phần tử nhỏ thứ 4 của : gom các cặp (giá trị, độ dài) , sắp xếp thành , đi dần: sau ba cặp đầu đã qua 3 phần tử, cặp thứ tư chứa phần tử thứ 4: đáp án 5.
5. Tổng : .
Cả hai kết quả và đều được in ra từ chương trình ở mục Cài đặt (và khớp với vét cạn). Để ý sau bước 3, hai khối cạnh nhau không bao giờ bị gộp tự động; với bài cần đếm "khối cực đại" như icpc25natg, phải tự gộp khối mới với hai khối bên cạnh khi chúng cùng giá trị.
Cài đặt
Chương trình đọc , , mảng , rồi thao tác (chỉ số từ 1):
1 l r x: gán ;2 l r x: cộng vào ;3 l r k: in phần tử nhỏ thứ của ;4 l r: in tổng (giả sử vừalong long).
Bản C++ dùng std::map. Python không có cây cân bằng sẵn, nên dùng hai danh sách song song starts/vals cùng bisect; chèn và xóa giữa danh sách tốn nhưng là thao tác dịch bộ nhớ rất nhanh, đủ dùng khi số khối được giữ nhỏ.
#include <bits/stdc++.h>
using namespace std;
// Chtholly tree: mảng được lưu thành các khối liên tiếp cùng giá trị.
// odt[p] = giá trị của khối bắt đầu tại p; khối kéo dài tới ngay trước khối kế tiếp.
map<int, long long> odt;
// Đảm bảo có một khối bắt đầu đúng tại p, trả về iterator tới khối đó.
map<int, long long>::iterator split(int p) {
auto it = prev(odt.upper_bound(p)); // khối đang chứa p
if (it->first == p) return it;
return odt.emplace_hint(next(it), p, it->second); // nửa sau giữ nguyên giá trị
}
void assign(int l, int r, long long x) { // a[l..r] = x
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr); // xóa mọi khối trong [l, r] ...
odt[l] = x; // ... và thay bằng đúng một khối
}
void add(int l, int r, long long x) { // a[l..r] += x
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; ++it) it->second += x;
}
long long kth(int l, int r, int k) { // phần tử nhỏ thứ k của a[l..r]
auto itr = split(r + 1), itl = split(l);
vector<pair<long long, int>> blocks; // (giá trị, độ dài)
for (auto it = itl; it != itr; ++it) blocks.push_back({it->second, next(it)->first - it->first});
sort(blocks.begin(), blocks.end());
for (auto [v, len] : blocks) {
if (k <= len) return v;
k -= len;
}
return -1; // không xảy ra khi 1 <= k <= r - l + 1
}
long long sum(int l, int r) { // tổng a[l..r]
auto itr = split(r + 1), itl = split(l);
long long s = 0;
for (auto it = itl; it != itr; ++it) s += it->second * (next(it)->first - it->first);
return s;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
odt[i] = x; // ban đầu mỗi phần tử là một khối
}
odt[n + 1] = 0; // khối cầm canh: mọi khối thật đều có khối kế tiếp
while (q--) {
int t, l, r;
cin >> t >> l >> r;
if (t == 1) {
long long x;
cin >> x;
assign(l, r, x);
} else if (t == 2) {
long long x;
cin >> x;
add(l, r, x);
} else if (t == 3) {
int k;
cin >> k;
cout << kth(l, r, k) << "\n";
} else {
cout << sum(l, r) << "\n";
}
}
}
import sys
from bisect import bisect_right
def main():
# Chtholly tree: starts[i] là vị trí đầu khối thứ i, vals[i] là giá trị của khối đó;
# khối thứ i kéo dài tới starts[i + 1] - 1. Có khối cầm canh tại n + 1.
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
starts = list(range(1, n + 2))
vals = [int(x) for x in data[2 : 2 + n]] + [0]
def split(p):
"""Đảm bảo có một khối bắt đầu đúng tại p, trả về chỉ số của khối đó."""
i = bisect_right(starts, p) - 1 # khối đang chứa p
if starts[i] == p:
return i
starts.insert(i + 1, p) # nửa sau giữ nguyên giá trị
vals.insert(i + 1, vals[i])
return i + 1
out = []
p = 2 + n
for _ in range(q):
t, l, r = int(data[p]), int(data[p + 1]), int(data[p + 2])
if t == 4:
p += 3
else:
x = int(data[p + 3])
p += 4
il = split(l) # tách l trước: chèn tại r + 1 nằm sau il nên không làm dịch il
ir = split(r + 1)
if t == 1: # a[l..r] = x: thay mọi khối trong [l, r] bằng đúng một khối
starts[il:ir] = [l]
vals[il:ir] = [x]
elif t == 2: # a[l..r] += x
for i in range(il, ir):
vals[i] += x
elif t == 3: # phần tử nhỏ thứ x của a[l..r]
blocks = sorted((vals[i], starts[i + 1] - starts[i]) for i in range(il, ir))
for v, length in blocks:
if x <= length:
out.append(v)
break
x -= length
else: # tổng a[l..r]
out.append(sum(vals[i] * (starts[i + 1] - starts[i]) for i in range(il, ir)))
print("\n".join(map(str, out)))
main()
Độ phức tạp
Gọi là số khối nằm trong đoạn của thao tác, là tổng số khối hiện có.
| Thao tác | Thời gian (C++, std::map) |
|---|---|
split(p) |
|
| Gán đoạn | , và xóa khối |
| Cộng đoạn, tổng đoạn | |
| Phần tử nhỏ thứ |
Chỉ có phép gán (cùng các truy vấn mà mọi khối duyệt qua đều bị xóa ngay sau đó): mỗi thao tác tạo tối đa 3 khối mới, mỗi khối bị xóa tối đa một lần, nên tổng và tổng thời gian . Đây là trường hợp bảo đảm chắc chắn.
Có thao tác chỉ duyệt mà không xóa: tổng chi phí bằng tổng số khối được duyệt, không có cận tốt trong trường hợp xấu nhất (). Với dữ liệu ngẫu nhiên kiểu bài gốc, số khối giảm rất nhanh và thực tế chạy như . Trên máy thử, thao tác ngẫu nhiên bốn loại: C++ khoảng 0,07 giây, Python khoảng 0,2 giây.
⚠️ Lỗi thường gặp
- Thứ tự hai lần
split: với cài đặt kiểuset<Node>màsplitxóa rồi chèn lại khối, phải gọisplit(r + 1)trướcsplit(l); làm ngược lại thìsplit(r + 1)có thể xóa chính khối mà iterator củasplit(l)đang trỏ tới. Với hai danh sách song song (bản Python ở trên) thì ngược lại: phải tách trước, vì chèn một khối ở trước vị trí làm dịch chỉ số đã lấy. Lỗi này chạy đúng phần lớn test và chỉ sai khi và cùng nằm trong một khối. - Quên khối cầm canh: không có khối tại thì
split(n + 1)và phép tính độ dài khối cuối cùng (next(it)->first - it->first) truy cập ra ngoài cây. - Dùng cho dữ liệu cố ý xấu: đề có cộng đoạn và truy vấn đoạn nhưng không bảo đảm ngẫu nhiên thì người ra đề có thể gán từng điểm xen kẽ rồi hỏi cả mảng, làm mỗi truy vấn duyệt khối và TLE. Khi đó dùng Segment Tree có lazy propagation.
- Không gộp khối kề nhau cùng giá trị khi bài cần khối cực đại: cấu trúc chỉ bảo đảm mỗi khối có một giá trị, không bảo đảm hai khối cạnh nhau khác giá trị. Bài đếm độ dài các đoạn cực đại phải tự gộp sau mỗi phép gán.
- Tràn số khi tính tổng hay lũy thừa:
giá trị * độ dàicó thể vượtint; trong bài gốc phải tính bằng lũy thừa nhanh trên từng khối rồi nhân với độ dài, nhớ lấy modulo cả độ dài. - Khởi tạo mỗi phần tử một khối rồi chỉ hỏi, không gán: khi không có phép gán nào, cấu trúc suy biến thành mảng khối và mỗi truy vấn là ; nếu đề cho phép thì gộp sẵn các phần tử liên tiếp bằng nhau ngay từ đầu.
Biến thể / Mở rộng
- Kết hợp với cấu trúc đếm theo khối: duy trì thêm một Fenwick Tree (hoặc mảng đếm) theo độ dài khối hay theo giá trị khối, cập nhật mỗi khi một khối được tạo hay bị xóa. Truy vấn thống kê toàn cục khi đó không cần duyệt khối.
- Sắp xếp đoạn trên xâu ít ký tự: sau khi sắp xếp, đoạn chỉ còn tối đa 26 khối (mỗi chữ cái một khối), nên "sắp xếp đoạn" là gom số lượng từng chữ trong các khối rồi chèn lại tối đa 26 khối.
- Đếm khoảng trống / phủ đoạn: bài "đánh dấu đoạn làm việc hay nghỉ, hỏi tổng số ngày làm việc" chỉ có phép gán, nên Chtholly tree có độ phức tạp bảo đảm, với tới mà không cần nén tọa độ.
- Thay thế chắc chắn hơn: segment tree có lazy gán đoạn, Segment Tree Beats cho các phép chmin/chmax, hoặc Sqrt Decomposition với mỗi khối căn lưu cờ "cả khối cùng giá trị".
Bài tập luyện
- Làm đẹp xâu (icpc25natg): (Hard) Gán ký tự cho đoạn và hỏi số ký tự ít nhất cần xóa để không còn khối dài hơn ; đáp án chỉ phụ thuộc vào độ dài các khối cực đại, nên giữ các khối bằng Chtholly tree (nhớ gộp khối cùng ký tự) và hai Fenwick theo độ dài khối.
- Nhiệm vụ đơn giản (sortsubstr): (Expert) Sắp xếp tăng hoặc giảm từng đoạn con của xâu chữ thường; mỗi lần sắp xếp xóa các khối trong đoạn và chèn lại tối đa 26 khối.
- Tô màu dải ruy băng (ribpaint): (Expert) Tô màu đoạn, mỗi ô tăng độ rực rỡ bằng độ chênh màu, hỏi tổng độ rực rỡ đoạn; mỗi phép tô duyệt các khối trong đoạn, cộng cho cả khối vào một Fenwick tổng đoạn rồi xóa khối, nên mỗi khối bị xóa tối đa một lần và tổng chi phí được bảo đảm .
- Số ngày làm việc (workdays): (Expert) Gán đoạn ngày làm việc hoặc nghỉ với tới , sau mỗi lệnh in tổng số ngày làm việc; chỉ có phép gán nên Chtholly tree chạy trong khấu hao.
Bình luận