cpp-040Bước 1Nâng cao
Phân rã căn bậc hai: Thuật toán Mo đếm phần tử phân biệt
Hệ thống giám sát bảo mật của AI Empire Academy ghi nhận N mã sự kiện A1, A2, …, AN (1 ≤ Ai ≤ 105). Đội ngũ vận hành cần trả lời Q câu hỏi ngoại tuyến: trong đoạn sự k…
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Cấu trúc dữ liệu truy vấn đoạn (Segment Tree & BIT) C++
Xử lý các bài toán vừa cập nhật giá trị vừa truy vấn tổng hoặc cực trị đoạn trong thời gian O(log N), đáp ứng dữ liệu lên tới hàng triệu thao tác.
9
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
0
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
0
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
9
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Cây Fenwick (Binary Indexed Tree)
Thao tác bit i & (-i), cập nhật điểm và truy vấn tổng tiền tố trong O(log N).
Bước 2
Cây phân đoạn (Segment Tree)
Xây dựng cây 4*N nút, truy vấn max/min đoạn và cập nhật một điểm.
Bước 3
Kỹ thuật Lazy Propagation
Tối ưu hóa thao tác cập nhật trên cả một đoạn [L, R] trong thời gian O(log N).
Lỗi thường gặp & Cách phòng tránh
•
Khai báo kích thước mảng Segment Tree quá nhỏ (cần tối thiểu 4 * N phần tử).
•
Quên đẩy giá trị lười (push down lazy) xuống các nút con trước khi truy vấn.
Danh sách bài tập thực hành (9 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Nâng cao 9 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-056Bước 2Nâng cao
Implicit Treap: Thao tác Mảng Động
Cài đặt một mảng động hỗ trợ các thao tác chèn, xóa và đảo ngược đoạn (reverse) bằng cấu trúc dữ liệu Implicit Treap (Cartesian Tree with Random Priorities).
cpp-106Bước 3Nâng cao
Implicit Treap: Biến đổi Afin đoạn (Range Affine Transformation)
Cho một dãy gồm N số nguyên A1, A2, …, AN. Bạn cần xử lý Q truy vấn thuộc 2 loại:
cpp-030Bước 4Nâng cao
Bảng thưa Sparse Table cho truy vấn cực tiểu đoạn RMQ tĩnh
Trong hệ thống giám sát hạ tầng GPU/CPU phân tán của AI Empire Academy, các thông số tải đo lường theo từng giây được thu thập vào một mảng tĩnh gồm N số nguyên A1, A2, …, A…
cpp-078Bước 5Nâng cao
Cây phân đoạn bền vững: Tìm phần tử nhỏ thứ K trong đoạn
Cho một dãy gồm N số nguyên A1, A2, …, AN. Bạn cần trả lời Q truy vấn độc lập, mỗi truy vấn gồm 3 số L, R, K (1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ R - L + 1): Tìm phần tử có giá…
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-171Bước 6Nâng cao
DSU Có Hoàn Tác - Tính Liên Thông Động Ngoại Tuyến (Dynamic Connectivity)
Ban đầu có một đồ thị rỗng gồm N đỉnh (đánh số từ 1 đến N) và không có cạnh nào.
cpp-079Bước 7Nâng cao
Cây phân đoạn nâng cao: Segment Tree Beats (Chmin và Tính tổng)
Cho một dãy gồm N số nguyên A1, A2, …, AN. Bạn cần xử lý Q truy vấn thuộc 2 loại:
cpp-021Bước 8Nâng cao
Cây chỉ số nhị phân Fenwick Tree cập nhật điểm và tính tổng đoạn
Hệ thống Gateway của AI Empire Academy phân bổ tài nguyên cho N tài khoản người dùng được đánh số từ 1 đến N (1 ≤ N ≤ 105). Ban đầu, mỗi tài khoản i đã sử dụng một lượng token…
cpp-022Bước 9Nâng cao
Cây phân đoạn Segment Tree tìm giá trị nhỏ nhất đoạn động
Hệ thống giám sát cụm tính toán AI của AI Empire Academy theo dõi độ trễ mạng của N máy chủ được đánh số từ 1 đến N (1 ≤ N ≤ 105). Ban đầu, máy chủ thứ i có độ trễ là Ai (0…