Hỏi về cây chỉ số nhị phân (Fenwick Tree)

#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

image
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
#2

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) :slight_smile:

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
#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 ạ

#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 :smiley:

1 Like
#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
#6

Làm ntn thì phải giới hạn miền giá trị :smiley:

1 Like
#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
#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 :smiley:

2 Likes
#9

ờm đúng rồi :triumph:

đề dỏm đáng lẽ cho a_i ko giới hạn mới đúng :triumph:

1 Like
#11

Em cảm ơn 2 bác nhiều nha ^^, em hiểu rồi

#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
#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
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?