Interval Tree

Cây đoạn là 1 cấu trúc dữ liệu thường gặp trong các bài toán tin và nó trở nên vô cùng lợi hại trong các vấn đề yêu cầu tìm kiếm nhiều lần.

1. Đặt vấn đề:

Cho dãy số nguyên A gồm N phần tử đánh số từ 0 đến N-1. Có M yêu cầu, mỗi yêu cầu có 2 dạng:
     dạng 1 : 1 i u : với ý nghĩa gán A[i] = u
     dạng 2 : 2 l r : với ý nghĩa tìm max trong đoạn A[l] A[l+1] ..... A[r]
Giới hạn : N < 10^5, M < 10^5,-2^31<=A[i], u <= 2^31 -1, 0<=l<=r<=N-1, 0<=i<=N-1 .

ví dụ : N= 5, A= 1 , 2 , 3 , 4 , 5
1 1 3  => A = 1 3 3 4 5
2 1 2 => 3
1 1 7 => A = 1 , 7 , 3 , 4 ,5
2 1 3 => 7


Giải thuật "Thơ ngây" :
-  Với yêu cầu 1 thì ta chỉ dùng câu lệnh : A[i] = u;
- Với yêu cầu 2 ta làm như sau :
                              maxx=-2^31;
                              for(i=l;i<=r;i++)
                                        maxx=max(maxx,A[i]);
                              cout << maxx << endl;
- Độ phức tạp : M yêu cầu, mỗi yêu cầu duyệt khoảng N số, như vậy đpt là O(M*N) (khoảng ~ 10 tỷ) ~> sẽ bị time limited.

2.Interval Tree:

- Với cấu trúc dữ liệu này, chúng ta sẽ giải bài toán tin này trong thời gian M*logN. Tức là duyệt M yêu cầu, mỗi yêu cầu tìm max sẽ thực hiện trong logN.

- Interval tree là 1 cây nhị phân. 

- Ta sẽ biểu diễn IT (interval tree) bằng mảng. Với:

        T[0] là gốc của cây

        T[i<<1 +1] và T[i<<1+2] là nút con của T[i] ( Lưu ý: a<<n = a* (2^n) )

         

- Ví dụ với mảng A gồm 4 phần tử thì IT sẽ biểu diễn như sau

(H1)

** Nhận xét : Mỗi nút có 2 nút con (vì IT là cây nhị phân mà)

- Theo đúng cách biểu diễn T[i<<1+1] và T[i<<1+2] là con của T[i] (T[1] và T[2] là con của T[0] chẳng hạn)

   - Interval tree là 1 cây nhị phân, với mỗi lá sẽ đại diện cho 1 phần tử trong mảng theo đúng thứ tự.

    (Mảng A có 4 phần tử theo thứ tự A[0] A[1] A[2] A[3] )

- Rồi, cơ bản là đã hình dung đc 1 chút gì đó về IT. 

- IT có 1 tính chất như sau : Nút cha T[i] sẽ đại diện cho tất cả các phần tử do nút con của T[i] đại diện. 

    Ví dụ : như hình trên (H1) T[3] -> A[0], T[4] -> A[1], T[1] là cha của T[3] và T[4] => T[3] đại diện cho đoạn A[0],A[1].

Hoàn toàn tương tự : T[2] đại diện cho đoạn A[2],A[3]

Lại làm tương tự : T[0] đại diện cho đoạn A[0...3].

(H2)

- Nút đại diện cho 1 đoạn nào đó sẽ lưu thông tin của đoạn đó.

Thông tin ở đây là gì? Cái này tùy theo đề bài. Theo bài mà chúng ta đặt ra ban đầu thì thông tin đc lưu của 1 đoạn chính là max của đoạn đó.

Ví dụ A = 2, 7, 1, 8

- Các bạn dựa vào hình có thể thấy rõ T[3]=2 vì T[3] chỉ quản lí thông tin mỗi A[0] mà thôi.

nhưng T[1]=7, vì T[1] lưu thông tin A[0] A[1].

Hay T[0] = 8 vì nó lưu thông tin cả dãy số A.

- IT cũng không đến nỗi khó hiểu phải không nào :)

3. Xây dựng IT:

- Ta thấy nút gốc (T[0]) có độ sâu = 0, các nút con của gốc có độ sâu = 1.

- Nút T[i] có độ sâu k thì nút con của T[i] ( tức là T[i<<1+1] và T[i<<1+2]) có độ sâu k+1.

- Ta thấy ở độ sâu 0 có 1 nút, ở độ sâu 1 có 2 nút, độ sâu 2 có 4 nút => độ sâu k có 2^k nút (cái này dễ dàng chứng minh được).

- Vậy cây có độ sâu depth thì tổng số nút là 2^0 + 2^1 + 2^ 2 +....+ 2^depth.

- Các nút lá chính là các nút có độ sâu depth => có 2^depth nút lá.

*** Tính chất: 2^k-1 = 2^0+2^1+2^2+...+2^(k-1) => cây có 2^depth-1 + 2^depth

                                                                                               (nút cha)     (nút lá)

=> T[2^depth-1] là nút lá đầu tiên.....T[2^(depth+1)-2] là nút lá cuối cùng.

- Mỗi nút lá đại diện cho 1 phần tử của mảng => số nút lá không được phép ít hơn số phần tử của mảng. 

Nảy sinh 1 vấn đề, các nút lá luôn có số lượng dạng 2^k, vậy để biểu diễn 1 mảng có N=6 phần tử thì làm thế nào.?

  Trả lời: lúc này số các nút lá không thể là 4 < 6 (độ sâu = 2), vì vậy số các nút lá phải là 8 (độ sâu = 3), và ta sẽ thêm 1 số các phần tử ảo vào mảng ban đầu cho đủ 8 phần tử. Kết quả bài toán sẽ ko bị ảnh hưởng, vì mọi yêu cầu đều chỉ xoay quanh các phần tử từ 0 đến 5, các phần tử ảo thêm vào không ảnh hưởng.

OK, bắt đầu code.

Mảng số nguyên A, N phần tử.

Cây interval tree T, độ sâu depth,  chỉ số nút lá đầu tiên FirstB=2^depth-1, số nút lá numL=2^depth.

Let's code :)

Code C++ https://ideone.com/3djQsA

have fun ^.^

                               -- Thomas --