UNIEDU - Thuật toán ứng dụng | Segment Tree (Cây phân đoạn) & Tìm kiếm nhị phân

Bài giảng Thuật toán ứng dụng (UNIEDU): Segment Tree (cây phân đoạn) — cập nhật một phần tử và lấy max trên đoạn trong O(log n), cùng tìm kiếm nhị phân với cách code chuẩn không bị lặp vô hạn. ⏱ TIMELINE 0:00:00 Bài toán: cập nhật phần tử và tìm max đoạn [L, R] 0:00:35 Cách làm trâu và độ phức tạp O(n × q) 0:04:42 Ý tưởng Segment Tree 0:06:03 Cây nhị phân: mỗi nút quản lý một đoạn 0:09:39 Quy tắc id × 2, id × 2 + 1 và mid 0:10:35 Mỗi nút lưu giá trị cần lấy (max) của đoạn 0:11:49 Hàm update: ví dụ "sếp và sổ tay" 0:15:34 Ví dụ cập nhật a[3] 0:18:58 Code hàm update 0:27:06 Luồng chạy đệ quy của update 0:33:07 Dựng cây trong main, độ phức tạp O(log n) 0:35:45 Hàm get: 3 trường hợp 0:41:40 Ví dụ get(1, 1, n, 3, 8) 0:46:31 Ghép thành chương trình hoàn chỉnh 0:48:08 Độ phức tạp O(q log n) 0:48:54 Segment Tree, đệ quy và duyệt cây DFS 0:52:59 Tìm kiếm nhị phân: bài toán 0:53:47 Cách làm trâu O(q × n) 0:55:10 Ví dụ tìm số 8 trong dãy 0:57:28 Code tìm kiếm nhị phân chuẩn (L + 1 nhỏ hơn R) 0:58:45 Dấu bằng và cách cập nhật L, R 1:00:32 Vì sao cách này không bị lặp vô hạn 1:02:46 So sánh các cách code của học viên 1:04:50 Áp dụng vào bài: O(q log n) 1:05:39 Buổi sau: chặt nhị phân kết quả #UNIEDU #ThuatToanUngDung #SegmentTree #TimKiemNhiPhan #BinarySearch #CauTrucDuLieu #LapTrinhThiDau