Hỏi Về Cây Chỉ Số Nhị Phân (Fenwick Tree) - Dạy Nhau Học Trang chủ » Fenwick Tree Là Gì » Hỏi Về Cây Chỉ Số Nhị Phân (Fenwick Tree) - Dạy Nhau Học Có thể bạn quan tâm Fe+o2 Có Nhiệt độ Fe + O2 = Fe2o3 Cân Bằng Fe O2 Fe3o4 Là Phản ứng Gì Fe O2 = Feo điều Kiện Fe + O2 ở Nhiệt độ Cao Hỏi về cây chỉ số nhị phân (Fenwick Tree) programming algorithm data-structures duy_duy (duy duy) July 27, 2021, 10:39am #1 Là em mới học về cây chỉ số nhị phân cụ thể là tham khảo ở nguồn này ( Cây chỉ số nhị phân (Binary Indexed Tree) (vnoi.info)) và một số nguồn khác Em hiểu cái cách mà tạo ra cái cây, Nhưng khi em đọc cách giải bài tập đầu tiên bằng cách sử dụng Fenwick Tree (Em đọc ở cái nguồn em đưa ở trên á) em có khá thắc mắc rằng: Cụ thể trong thao tác tìm tổng của lời giải bài ghi là Để tìm tổng các phần tử trong đoạn [1…n], ta sẽ lần lượt đi qua tất cả bit của n theo giá trị tăng dần. Mỗi lần đi qua nn, ta sẽ cộng bit[n] vào kết quả hiện tại, rồi trừ đi bit nhỏ nhất của n khỏi chính nó; quá trình lặp lại cho đến khi n=0. Em có thắc mắc là bit nhỏ nhất của một số n là gì?, Em có search trên mạng thì thấy không có. Rồi phải tại sao phải trừ đi bit nhỏ nhất của chỉnh nó ạ? Ngoài ra, web còn bảo rằng kiến thức cây chỉ số Nhị Phân có thể áp dụng cho bài bài tập này image884×211 11.2 KB Em nghĩ mãi vẫn không ra được mối quan hệ giữa cây chỉ số Nhị Phân và bài tập này ạ. Xin mọi người giúp em ạ Em cảm ơn^^ 1 Like rogp10 (rogp10) July 27, 2021, 1:00pm #2 duy_duy: Rồi phải tại sao phải trừ đi bit nhỏ nhất của chỉnh nó ạ? Vì cây BIT là prefix sum được “nâng cấp” lên (với l = r - 1 << __builtin_ctz(r) thay vì l = 0) Bài này khá loằng ngoằng nhưng đại khái bạn tìm rank của các phần tử trong a rồi dùng thao tác cập nhật BIT tree. 2 Likes duy_duy (duy duy) July 27, 2021, 1:21pm #3 Dù không hiểu gì nhưng mà thôi cảm ơn bạn ^^ Bạn có cách nào giải bt dưới không? Có thì chỉ hướng mình với ạ rogp10 (rogp10) July 27, 2021, 6:16pm #4 Vì prefix sum cập nhật tăng giảm rất lâu nên người ta nghĩ ra cấu trúc này để cập nhật nhanh hơn. Một phần tử được tham chiếu bởi O(logN) ô nên mỗi thay đổi chỉ cần bao nhiêu đó bước, thay vì O(N). Nói về rank (hạng) của một số trong dãy thì bài này dùng định nghĩa là số số < nó trong dãy (ví dụ < là lớn hơn thì hạng 1 là lớn nhất). Định nghĩa BIT[i] là số số < hơn số thứ i trong dãy đến hiện tại 1 Like tntxtnt () July 29, 2021, 1:07pm #5 bài tập thì do a_i \leq 60000 nên tạo 1 mảng tần suất xuất hiện của a_i tạm gọi là freq, freq[x] là số lần xuất hiện của x trong mảng A. Ví dụ A = [2, 7, 1, 8, 2, 8] thì freq = [0, 1, 2, 0, 0, 0, 0, 1, 2]. Rồi dựng BIT cho mảng freq tạm gọi là itree. Sau đó với mỗi a[i] với i từ 0..n-1, lấy tổng itree.sum(a[i] - 1) = sum(freq[1]..freq[a[i] - 1]) là ra :V Trước khi xét tiếp a[i+1] thì bỏ a[i] ra khỏi freq bằng cách add itree.add(a[i], -1) là được :V vd A = [2, 7, 1, 8, 2, 8] freq = [0, 1, 2, 0, 0, 0, 0, 1, 2] i = 0: A[0] = 2 itree.sum(2 - 1) = itree.sum(1) = freq[0] + freq[1] = 1 bỏ A[0] = 2 ra khỏi freq: freq = [0, 1, 1, 0, 0, 0, 0, 1, 2] ^ i = 1: A[1] = 7 itree.sum(7 - 1) = itree.sum(6) = freq[0] + freq[1] + ... + freq[6] = 2 bỏ A[1] = 7 ra khỏi freq: freq = [0, 1, 1, 0, 0, 0, 0, 0, 2] ^ v.v... lười chạy tay quá :V xài BIT để tính sum với add O(\log n). Thực hiện n lần thì đpt là O(n \log n) 3 Likes rogp10 (rogp10) July 27, 2021, 3:08pm #6 Làm ntn thì phải giới hạn miền giá trị 1 Like tntxtnt () July 27, 2021, 3:13pm #7 đề cho a_i \leq 60000 mà :V Nếu là 10^{18} thì đâu có xài BIT được =] 10^9 chắc cũng ko được 1 Like rogp10 (rogp10) July 27, 2021, 3:15pm #8 Được mà, thay số thành hạng của nó trong dãy thì thành O(NlogN) thôi. Mảng bên dưới giống y như bảng tần suất vậy 2 Likes tntxtnt () July 27, 2021, 3:17pm #9 ờm đúng rồi đề dỏm đáng lẽ cho a_i ko giới hạn mới đúng 1 Like duy_duy (duy duy) July 28, 2021, 3:41am #11 Em cảm ơn 2 bác nhiều nha ^^, em hiểu rồi tntxtnt () July 28, 2021, 1:48pm #12 đi ngược cũng đúng, còn lẹ hơn đi xuôi nữa :V thay vì đi xuôi remove thì đi ngược add thêm vào :V 2 Likes rogp10 (rogp10) July 29, 2021, 5:21am #13 BIT tree ngoài dạng bắt đầu từ 1 còn có dạng bắt đầu từ 0: tính tổng: BITsum(0) := BIT[0] := a[0] với a là mảng bên dưới BITsum(k) := BITsum(k & (k+1) -1) + BIT[k] với & là phép AND bit. cập nhật: increaseBIT(k, v) := k < BITsize() && (BIT[k] += v, increaseBIT(k | (k+1), v)) với phép | là OR bit. đọc ô thứ k của mảng bên dưới: a[k] = BITsum(k) - BITsum(k-1) Dạng bắt đầu từ 1 thì do (0,1)*1(0)^m và (0,1)*0(1)^m có chung node cha nên thao tác đọc 1 ô là \Theta(m). 2 Likes DayNhauHoc's Discord Học C++ Free? Click Blog Dạy Nhau Học Tự Học Lập Trình 83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao? Từ khóa » Fenwick Tree Là Gì Cây Chỉ Số Nhị Phân (Binary Indexed Tree) - VNOI Fenwick Tree - Cây Chỉ Số Nhị Phân (Binary Indexed Tree) - VietCodes Cấu Trúc Dữ Liệu BIT – Binary Indexed Tree (Fenwick Tree) - Viblo Fenwick Tree | How Kteam [Đồ án] Cây Fenwick Tree (BIT) - Cây Chỉ Số Nhị Phân - YouTube Binary Indexed Tree (BIT) - NTUCoder - Bài Viết Cây Chỉ Số Nhị Phân (Binary Indexed Tree) - Codeforces Blog: Fenwick Tree - Txhai12 - OLP HOU Online Judge Binary Indexed Tree - Tuoitrekthc Cây Chỉ Mục Nhị Phân (Binary Indexed Tree) - Vallicon Binary Index Tree Trong Cơ Sở Dữ Liệu - Kipalog Cấu Trúc Dữ Liệu Binary Indexed Trees - Tài Liệu Text - 123doc Tài Liệu Cấu Trúc Dữ Liệu Binary Indexed Trees - Xemtailieu [DOC] Học Binary Indexed Trees Từ Các Kĩ Thuật đơn Giản Nhất.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?