Wavelet Tree
Cấu trúc dữ liệu tĩnh chia mảng theo giá trị và giữ thứ tự theo vị trí, trả lời phần tử nhỏ thứ k và đếm phần tử nhỏ hơn ngưỡng trên một đoạn trong O(log n). Có ví dụ chạy tay, cài đặt C++/Python và giới thiệu dạng wavelet matrix.
Wavelet tree là cấu trúc dữ liệu tĩnh trên một mảng trả lời các câu hỏi thống kê thứ tự trên đoạn trong mỗi truy vấn ( là số giá trị khác nhau):
- phần tử nhỏ thứ của (từ đó có trung vị đoạn);
- số phần tử (hoặc trong khoảng ) của ;
- số lần xuất hiện của một giá trị, tổng phần tử nhỏ nhất (nếu lưu thêm tổng tiền tố)...
Nó làm được cùng việc với Persistent Segment Tree nhưng gọn hơn, bộ nhớ số nguyên nhỏ, và có thể trả lời online. Với , dựng cây mất , mỗi truy vấn khoảng bước.
Ý tưởng / Trực giác
Chia theo giá trị, giữ thứ tự theo vị trí. Nút gốc phụ trách khoảng giá trị (toàn bộ giá trị sau khi nén tọa độ) và chứa cả dãy. Lấy : phần tử có giá trị đi sang con trái, còn lại sang con phải, giữ nguyên thứ tự tương đối (chia ổn định). Lặp lại đệ quy cho tới khi khoảng giá trị chỉ còn một số. Cây có độ cao , và mỗi phần tử xuất hiện đúng một lần ở mỗi tầng.
Chỉ cần một mảng đếm mỗi nút. Tại mỗi nút ta lưu
Bổ đề then chốt (ánh xạ đoạn). Nếu một đoạn vị trí ở nút hiện tại, thì các phần tử của nó đi sang trái chiếm đúng đoạn ở con trái, và các phần tử đi sang phải chiếm đúng đoạn ở con phải. Lý do: chia ổn định nên phần tử thứ đi trái có vị trí mới bằng số phần tử đi trái trong phần tử đầu, và tương tự bên phải với "số phần tử đi phải" . Một đoạn con liên tiếp vì thế luôn biến thành đúng một đoạn liên tiếp ở mỗi con.
Tìm phần tử nhỏ thứ . Ở nút hiện tại, là số phần tử của đoạn có giá trị . Nếu , đáp án nằm bên trái: đi xuống con trái với đoạn đã ánh xạ. Ngược lại đáp án nằm bên phải và là phần tử nhỏ thứ trong phần bên phải. Tới lá thì khoảng giá trị chỉ còn một số: đó là đáp án. Đây chính là tìm kiếm nhị phân trên giá trị, nhưng mỗi bước nhờ mảng .
Đếm phần tử . Đi đồng thời xuống các nút: nút nằm hẳn dưới () đóng góp toàn bộ độ dài đoạn, nút nằm hẳn trên () đóng góp , còn lại tách xuống hai con. Giống truy vấn trên segment tree, chỉ có nút bị tách.
Wavelet matrix. Một cách cài khác (hay gặp trong lời giải ICPC) là chia theo từng bit từ bit cao xuống bit thấp, mỗi tầng là một dãy bit độ dài thay vì nhiều nút. Ý tưởng ánh xạ đoạn y hệt, nhưng toàn bộ tầng nằm trong một mảng nên ít cấp phát và nhanh hơn. Trang này cài dạng cây để dễ hình dung; chuyển sang dạng ma trận không đổi gì về thuật toán.
Ví dụ chạy tay
Mảng (giá trị từ 1 tới 6, nên không cần nén). Ký hiệu bit là "sang trái" (), là "sang phải". Cây được dựng như sau (in ra từ chương trình):
[1,6] mid=3 dãy 3 1 4 1 5 2 6 2
bit 0 0 1 0 1 0 1 0
b 0 1 2 2 3 3 4 4 5
├─ [1,3] mid=2 dãy 3 1 1 2 2
│ bit 1 0 0 0 0
│ b 0 0 1 2 3 4
│ ├─ [1,2] mid=1 dãy 1 1 2 2 bit 0 0 1 1 b 0 1 2 2 2
│ │ ├─ [1,1] lá: 1 1
│ │ └─ [2,2] lá: 2 2
│ └─ [3,3] lá: 3
└─ [4,6] mid=5 dãy 4 5 6
bit 0 0 1
b 0 1 2 2
├─ [4,5] mid=4 dãy 4 5 bit 0 1 b 0 1 1
│ ├─ [4,4] lá: 4
│ └─ [5,5] lá: 5
└─ [6,6] lá: 6
Truy vấn: phần tử nhỏ thứ 3 của (sắp xếp: , đáp án là ):
| Nút | Đoạn | Số đi trái | Quyết định | |||
|---|---|---|---|---|---|---|
| [1,6] | [2, 7] | 3 | 1 | 4 | 3 | : sang trái, đoạn mới |
| [1,3] | [2, 4] | 3 | 0 | 3 | 3 | : sang trái, đoạn mới |
| [1,2] | [1, 3] | 3 | 0 | 2 | 2 | : sang phải, , đoạn mới |
| [2,2] | [1, 1] | 1 | lá: đáp án 2 |
Truy vấn: phần tử nhỏ thứ 5 của cùng đoạn (đáp án ): ở gốc nên sang phải với , đoạn (chính là ). Ở nút [4,6], : sang trái, đoạn (là ). Ở nút [4,5], : sang phải với , tới lá [5,5]: đáp án 5.
Truy vấn: số phần tử trong : ở gốc, con trái [1,3] nằm hẳn dưới nên đóng góp cả đoạn đã ánh xạ , tức phần tử (). Con phải [4,6] có đoạn , tách tiếp: nút [4,5] nhận đoạn , rồi lá [4,4] nhận phần tử. Tổng , khớp với đếm tay .
Cài đặt
Chương trình đọc , , mảng (giá trị bất kỳ trong long long, có thể âm), rồi truy vấn dạng 1 l r k (in phần tử nhỏ thứ của ) hoặc 2 l r x (in số phần tử trong ). Chỉ số từ 1. Giá trị được nén về trước khi dựng cây, nên độ cao là .
#include <bits/stdc++.h>
using namespace std;
// Wavelet tree trên giá trị đã nén về [0, sigma). Mỗi nút giữ khoảng giá trị [lo, hi]
// và mảng b: b[i] = số phần tử trong i phần tử đầu của nút đi sang con trái (giá trị <= mid).
struct WaveletTree {
int lo, hi;
WaveletTree *L = nullptr, *R = nullptr;
vector<int> b;
WaveletTree(int* from, int* to, int x, int y) : lo(x), hi(y) {
if (lo == hi || from >= to) return; // lá, hoặc nút rỗng
int mid = (lo + hi) / 2;
auto goLeft = [mid](int v) { return v <= mid; };
b.reserve(to - from + 1);
b.push_back(0);
for (int* it = from; it != to; ++it) b.push_back(b.back() + goLeft(*it));
int* pivot = stable_partition(from, to, goLeft); // giữ nguyên thứ tự tương đối
L = new WaveletTree(from, pivot, lo, mid);
R = new WaveletTree(pivot, to, mid + 1, hi);
}
// phần tử nhỏ thứ k (k từ 1) trong đoạn [l, r] của nút (chỉ số từ 1)
int kth(int l, int r, int k) {
if (lo == hi) return lo;
int lb = b[l - 1], rb = b[r]; // số phần tử sang trái trước l và tới hết r
int inLeft = rb - lb;
if (k <= inLeft) return L->kth(lb + 1, rb, k);
return R->kth(l - lb, r - rb, k - inLeft); // vị trí bên phải = vị trí - số đi trái
}
// số phần tử có giá trị <= x trong đoạn [l, r]
int leq(int l, int r, int x) {
if (l > r || x < lo) return 0;
if (hi <= x) return r - l + 1; // cả nút nằm dưới ngưỡng
int lb = b[l - 1], rb = b[r];
return L->leq(lb + 1, rb, x) + R->leq(l - lb, r - rb, x);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (auto& x : a) cin >> x;
vector<long long> vals(a); // nén giá trị
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
vector<int> c(n);
for (int i = 0; i < n; i++) c[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
WaveletTree wt(c.data(), c.data() + n, 0, (int)vals.size() - 1); // c bị sắp lại, không dùng nữa
while (q--) {
int t, l, r;
long long x;
cin >> t >> l >> r >> x;
if (t == 1) { // "1 l r k": phần tử nhỏ thứ k của a[l..r]
cout << vals[wt.kth(l, r, (int)x)] << "\n";
} else { // "2 l r x": số phần tử <= x trong a[l..r]
int id = upper_bound(vals.begin(), vals.end(), x) - vals.begin() - 1;
cout << (id < 0 ? 0 : wt.leq(l, r, id)) << "\n";
}
}
}
import sys
from bisect import bisect_right
class WaveletTree:
"""Wavelet tree trên giá trị đã nén về [0, sigma). Mỗi nút giữ khoảng giá trị [lo, hi]
và mảng b: b[i] = số phần tử trong i phần tử đầu của nút đi sang con trái (giá trị <= mid)."""
def __init__(self, arr, lo, hi):
self.lo, self.hi = lo, hi
self.L = self.R = None
if lo == hi or not arr: # lá, hoặc nút rỗng
return
mid = (lo + hi) // 2
b = [0]
cnt = 0
left, right = [], []
for v in arr: # chia ổn định: giữ nguyên thứ tự tương đối
if v <= mid:
cnt += 1
left.append(v)
else:
right.append(v)
b.append(cnt)
self.b = b
self.L = WaveletTree(left, lo, mid)
self.R = WaveletTree(right, mid + 1, hi)
def kth(self, l, r, k):
"""Phần tử nhỏ thứ k (k từ 1) trong đoạn [l, r] của nút (chỉ số từ 1)."""
node = self
while node.lo != node.hi:
lb, rb = node.b[l - 1], node.b[r] # số phần tử sang trái trước l và tới hết r
if k <= rb - lb:
node, l, r = node.L, lb + 1, rb
else:
k -= rb - lb
node, l, r = node.R, l - lb, r - rb # vị trí bên phải = vị trí - số đi trái
return node.lo
def leq(self, l, r, x):
"""Số phần tử có giá trị <= x trong đoạn [l, r]."""
if l > r or x < self.lo:
return 0
if self.hi <= x: # cả nút nằm dưới ngưỡng
return r - l + 1
lb, rb = self.b[l - 1], self.b[r]
return self.L.leq(lb + 1, rb, x) + self.R.leq(l - lb, r - rb, x)
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = list(map(int, data[2 : 2 + n]))
vals = sorted(set(a)) # nén giá trị
rank = {v: i for i, v in enumerate(vals)}
wt = WaveletTree([rank[v] for v in a], 0, len(vals) - 1)
out = []
p = 2 + n
for _ in range(q):
t, l, r, x = int(data[p]), int(data[p + 1]), int(data[p + 2]), int(data[p + 3])
p += 4
if t == 1: # "1 l r k": phần tử nhỏ thứ k của a[l..r]
out.append(vals[wt.kth(l, r, x)])
else: # "2 l r x": số phần tử <= x trong a[l..r]
idx = bisect_right(vals, x) - 1
out.append(0 if idx < 0 else wt.leq(l, r, idx))
print("\n".join(map(str, out)))
main()
Trên máy thử với : bản C++ khoảng 0,2 giây, bản Python khoảng 1,2 giây.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Nén giá trị | ||
| Dựng cây | ||
| Phần tử nhỏ thứ | ||
| Đếm phần tử |
Vì sao? Mỗi tầng của cây chứa mỗi phần tử đúng một lần, nên tổng kích thước mọi mảng ở một tầng là , và có tầng. Truy vấn -th đi đúng một đường từ gốc xuống lá, mỗi bước . Truy vấn đếm giống truy vấn đoạn trên segment tree: mỗi tầng có tối đa hai nút "dở dang" bị tách tiếp, nên cũng . Với , cây có tầng, khoảng số int, tức khoảng MB.
⚠️ Lỗi thường gặp
- Không nén giá trị: dựng trực tiếp trên khoảng làm cây cao tầng và có thể sinh rất nhiều nút; với giá trị âm,
(lo + hi) / 2trong C++ làm tròn về : ví dụ , cho , con trái nhận lại nguyên khoảng và đệ quy vô hạn. - Chia không ổn định: dùng
partitionthay chostable_partition(hoặc tự đổi chỗ phần tử) phá thứ tự vị trí, và bổ đề ánh xạ đoạn sai. Kết quả sai mà không báo lỗi. - Sai công thức ánh xạ sang con phải: đoạn bên phải là , không phải . Lệch một vị trí ở đây cho kết quả đúng trên nhiều test nhỏ và sai trên test lớn.
- Quên giảm khi sang phải: sang con phải phải tìm phần tử thứ , không phải thứ .
- Truy vấn đếm với ngưỡng chưa nén: ngưỡng trong truy vấn là giá trị gốc, phải đổi thành chỉ số của giá trị lớn nhất (
upper_bound - 1), và trả về khi không có giá trị nào . - Đệ quy dựng cây với lớn trong Python: độ sâu chỉ nên không tràn ngăn xếp, nhưng tạo hàng triệu đối tượng nút sẽ chậm và tốn bộ nhớ. Với Python, nên nén giá trị và dừng ở nút rỗng như code trên, hoặc chuyển sang dạng wavelet matrix (mỗi tầng một mảng).
Biến thể / Mở rộng
- Wavelet matrix: chia theo từng bit, mỗi tầng là một dãy bit với bảng đếm theo khối 64 bit (xem Bitset để hiểu kỹ thuật đếm bit nhanh). Bộ nhớ chỉ khoảng bit, nhanh hơn dạng cây và là dạng hay dùng nhất trong lời giải mẫu.
- Tổng của phần tử nhỏ nhất: lưu thêm mảng tổng tiền tố của giá trị ở mỗi nút; khi đi sang phải, cộng tổng các phần tử của đoạn đã ánh xạ sang trái.
- Đếm trong hình chữ nhật: với các điểm sắp theo , số điểm trong là
leqtrên đoạn chỉ số ứng với . Kết hợp với Euler tour hoặc thứ tự lá của Cây Kruskal, các câu hỏi "cây con" hay "thành phần" thành câu hỏi trên đoạn. - Có cập nhật: wavelet tree thuần là tĩnh. Đổi chỗ hai phần tử kề nhau vẫn làm được bằng cách sửa trên một đường; cập nhật tổng quát thì dùng Sqrt Decomposition (dựng lại định kỳ), cây phân đoạn lồng Fenwick, hoặc xử lý offline.
- So sánh nhanh: chỉ cần -th trên đoạn một lần cho vài truy vấn thì
nth_elementmỗi truy vấn là đủ; truy vấn offline có thể dùng Mo's Algorithm hoặc chặt nhị phân song song.
Bài tập luyện
- Cây con gốc v (lctst26_e): (Very Hard) Phần tử nhỏ thứ trong cây con; duyệt Euler biến cây con thành một đoạn liên tiếp, rồi đúng truy vấn -th trên đoạn.
- Tổng chênh lệch lớn nhất (tst25_arrng): (Very Hard) Đáp án mỗi truy vấn có công thức đóng theo dãy đã sắp xếp của đoạn, cần phần tử nhỏ thứ và tổng phần tử nhỏ nhất trên đoạn; wavelet tree lưu thêm tổng tiền tố ở mỗi tầng.
- Trung vị (icpc22mtd): (Very Hard) Hỏi trung vị của nhiều đoạn con; trung vị là phần tử nhỏ thứ của đoạn, đúng truy vấn -th của wavelet tree.
- Điệu valse (icpc25mbj): (Expert) Mảng bị xoay đoạn liên tục xen với truy vấn phần tử nhỏ thứ ; giữ một ảnh chụp tĩnh có wavelet matrix, mô tả mảng hiện tại bằng danh sách đoạn của ảnh chụp và đi xuống cây với nhiều đoạn cùng lúc, dựng lại theo chia căn.
- Hai đường đặc biệt (icpc22mnm): (Master) Chọn hai cạnh để tối đa số người phải trả phí; sau khi quy về các cặp cạnh trên cây DFS, mỗi lần tính giá trị là đếm điểm trong hình chữ nhật trên tọa độ Euler, trả lời bằng wavelet matrix.
Bình luận