Segment Tree

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 15:15 15-05-2022 93 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

Segment Tree

Dẫn nhập

Các cấu trúc dữ liệu liên quan đến đồ thị và cây được áp dụng rất nhiều trong thực tế. Trong bài học ngày hôm nay, chúng ta sẽ bắt đầu tìm hiểu về các cấu trúc dữ liệu có liên quan đến đồ thị và cây, mở đầu là Segment Tree. Hãy cùng tìm hiểu xem Segment Tree là gì nhé!


Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

  • Segment Tree

Bài toán đặt ra

Cho một dãy gồm n số nguyên a_{i} (n\leq 10^{5}, a_{i}\leq 10^{9}). Có q truy vấn thuộc 1 trong 2 dạng sau:

  •  U\ x\ y: Thay thế giá trị của a_{x} bằng y (|y|\leq 10^{9})
  • Q\ u\ v: In ra giá trị nhỏ nhất trong đoạn a_{u}, a_{u+1}, _{\cdot \cdot \cdot }, a_{v} (1\leq u\leq v\leq n)

Ví dụ:

Input Outout

7

3 5 2 6 9 1 2

6

Q 1 5

U 2 1

Q 1 5

U 6 4

U 7 9

Q 4 7

2

1

4

Giải thích ví dụ:

Ví dụ trên gồm có 6 truy vấn trong đó:

  • Truy vấn 1 yêu cầu in ra giá trị nhỏ nhất trong đoạn [1, 5] gồm các phần tử {3, 5, 2, 6, 9}. Do đó, giá trị nhỏ nhất trong đoạn này là 2. Ta in ra 2.
  • Truy vấn 2 thay đổi phần tử a2 thành 1. Khi này, dãy đã cho trở thành 3, 1, 2, 6, 9, 1, 2
  • Truy vấn 3 yêu cầu in ra giá trị nhỏ nhất trong đoạn [1, 5] gồm các phần tử {3, 1, 2, 6, 9}. Do đó, giá trị nhỏ nhất trong đoạn này là 1. Ta in ra 1.
  • Truy vấn 4 và 5 lần lượt thay giá trị của phần tử a6 thành 4 và a7 thành 9. Khi này, dãy đã cho trở thành 3, 1, 2, 6, 9, 4, 9
  • Truy vấn 6 yêu cầu in ra giá trị nhỏ nhất trong đoạn [4, 7] gồm các phần tử {6, 9, 4, 9}. Do đó, giá trị nhỏ nhất trong đoạn này là 4.

Đây chính là bài toán tổng quát hơn bài toán mà mình đã nêu ra ở bài Tìm kiếm min, max trên đoạn tịnh tiến.


Lời giải ban đầu

Vẫn theo một suy nghĩ thông thường, đề bài bảo gì ta sẽ làm đó. Do vậy:

  • Với truy vấn U, ta sẽ gán a_{x}=y
  • Với truy vấn Q, ta sẽ dùng vòng lặp duyệt từ u đến v để tìm phần tử nhỏ nhất

Với suy nghĩ như vậy, ta có thể code như sau:

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    int q;
    cin >> q;
    while(q--){
        char query;
        int x, y;
        cin >> query >> x >> y;
        if(query == 'U'){
            a[x] = y;
        }
        else{
            int minValue = 1e9;
            for(int i = x ; i <= y ; ++i) minValue = min(minValue, a[i]);
            cout << minValue << endl;
        }
    }

    return 0;
}

Tuy nhiên, các bạn có thể thấy ngay độ phức tạp của code trên là O(n \times q). Vậy thì liệu có cách nào tối ưu hơn phương pháp ở trên không?


Nhận xét

Bây giờ, hãy tạm thời bỏ lập trình qua một bên và nhìn vào một ví dụ trong thực tế.

Giả sử, bạn là người quản lí về dân cư của quốc gia. Bây giờ bạn cần lấy thông tin về tổng số dân của quốc gia. Vậy thì bạn sẽ làm gì?

Liệu bạn có đi đến gặp từng người trong cả quốc gia đó, mỗi lần gặp một người mới, bạn lại tăng kết quả đếm lên không? Chắc hẳn là không rồi đúng không vì làm như vậy thì rất mất thời gian và dễ xảy ra sai sót. Như vậy thì ta sẽ cần phải làm gì?

Ta sẽ gửi thông tin yêu cầu tính số dân đến từng tỉnh, mỗi tỉnh lại gửi yêu cầu tính số dân đến từng huyện, mỗi huyện lại gửi yêu cầu tính số dân đến từng xã, mỗi xã lại gửi yêu cầu tính số dân đến từng thôn. Khi này, trưởng thôn sẽ đi tính số dân của thôn mình rồi báo cáo lại. Xã, huyện và tỉnh từ kết quả báo cáo của cấp dưới sẽ tổng hợp số liệu để báo cáo lên cấp trên. Khi này, bạn chỉ cần tổng hợp số liệu từ các tỉnh là có thể thu được kết quả. Đây thực chất chính là chiến thuật “chia để trị”.

Với cách làm trên, giả sử số dân của một thôn nào đó có thay đổi thì thôn đó cũng chỉ cần báo cáo với xã quản lí thôn đó, xã lại báo cáo lên huyện, huyện báo cáo lên tỉnh và tỉnh sẽ báo cáo cho bạn. Từ đó, mọi sự thay đổi đều được cập nhật mà không gây ra ảnh hưởng cho các tỉnh khác.

Ý tưởng trên chính là ý tưởng của Segment Tree. Vậy thì chính xác Segment Tree là gì?


Segment Tree

Khái niệm

Segment Tree là một cây nhị phân với mỗi nút quản lí một đoạn thuộc dãy số. Nút gốc của cây sẽ quản lí đoạn [1, n]. Với mỗi nút cha quản lí đoạn [i, j] thì nút con trái sẽ quản lí đoạn [i, \frac{i+j}{2}], nút con phải sẽ quản lí đoạn [\frac{i+j}{2} +1,j].

Dưới đây là minh hoạ cho một cây Segment Tree quản lí đoạn 7 phần tử


Chuẩn bị

Có khá nhiều cách để code một Segment Tree nhưng trong khoá học này, mình sẽ hướng dẫn các bạn xây dựng Segment Tree như là một class vì mình cảm thấy đây là cách dễ hiểu và rõ ràng nhất.

Để có thể xây dựng Segment Tree ta sẽ cần các thành phần sau:

  • Ta sẽ đánh số các node trên cây theo thứ tự từ trái sang phải, từ trên xuống dưới. Nếu đánh số thứ tự như vậy thì ta thu được một tính chất như sau: Nếu số thứ tự của node cha là x thì số thứ tự của hai node con là x \times 2 và x \times 2 + 1.
  • Hai mảng low, high trong đó đoạn [low[index], high[index]] thể hiện cho đoạn mà node thứ index quản lý
  • Một mảng TNode trong đó  TNode[index] đại diện cho thông tin mà node thứ index quản lí. Như ở ví dụ trên thì TNode sẽ là một mảng số nguyên mà TNode[index] dùng để lưu trữ giá trị nhỏ nhất của đoạn mà node thứ index quản lý.
  • Các mảng low, high, TNode có kích thước là 4\times MaxN, có nghĩa là 4 lần độ dài tối đa của dãy mà Segment Tree quản lí.
  • Ta sẽ cần một mảng leaf trong đó leaf[i] thể hiện cho số thứ tự của node lá biểu diễn cho phần tử thứ i trong đoạn. Ý nghĩa của mảng này sẽ được đề cập trong phần sau.

Ví dụ cho một cây Segment Tree hoàn chỉnh:

Một Segment Tree sẽ chứa 3 phương thức cơ bản sau:

  • Build(): khởi tạo một cây
  • Update(): cập nhật các thay đổi của cây
  • Query(): Tiến hành các truy vấn trên cây

Cơ chế hoạt động

Hàm Build()

Hàm Build() sẽ là một hàm void nhận vào 3 tham số gồm:

  • index: là một số nguyên thể hiện cho số thứ tự của node đó
  • l, r: là 2 số nguyên thể hiện cho đoạn [l,r] mà node đó quản lí

Hàm Build() sẽ thực hiện các thao tác sau:

  • Ghi nhận lại đoạn mà node đó quản lí vào hai mảng low, high
  • Nếu như node hiện tại là node lá (tức là l=r) thì cập nhật giá trị cho TNode của node đó
  • Nếu như không phải là node lá, ta sẽ gọi đệ quy hàm Build() để khởi tạo hai node con trong đó node bên trái có số thứ tự là index \times 2 và quản lí đoạn [l,\frac{l+r}{2}], node bên phải có số thứ tự index \times 2 +1 và quản lí đoạn [\frac{l+r}{2} + 1,r]
  • Sau khi xây dựng xong hai nút con, ta sẽ cập nhật TNode của node hiện tại bằng TNode của hai node con tuỳ theo yêu cầu

Ở đây, mình sẽ xây dựng hàm Build() cho ví dụ ở đầu của chúng ta

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

class SegmentTree{

    int low[4 * MaxN], high[4 * MaxN], TNode[4 * MaxN], leaf[MaxN];

    public:
        void Build(int index, int l, int r){
            low[index] = l;
            high[index] = r;
            if(l == r){
                TNode[index] = a[l];
                leaf[l] = index;
                return;
            }
            Build(index * 2, l, (l + r) / 2);
            Build(index * 2 + 1, (l + r) / 2 + 1, r);
            TNode[index] = min(TNode[index * 2], TNode[index * 2 + 1]);
        } 

} SegmentTree;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    SegmentTree.Build(1, 1, n);

    return 0;
}


Hàm Query()

Hàm Query() là hàm sẽ trả về kết quả cần truy vấn của chúng ta và gồm 2 tham số là l, r thể hiện cho đoạn cần truy vấn.

Tiếp theo, ta sẽ cần đến một hàm Find(). Đây sẽ làm hàm trực tiếp đi tìm kết quả. Hàm Query() chỉ có tác dụng nhận yêu cầu và trả kết quả thu được từ hàm Find(). Vậy thì chính xác hàm Find() này sẽ làm gì?

Trước hết, ta sẽ cần 2 biến qi, qj mà qi=l, qj=r để có thể lưu lại truy vấn và sử dụng trong hàm Find(). Các bạn cũng có thể truyền l, r như hai tham số vào hàm Find() tuy nhiên như vậy thì sẽ khiến cho code dài dòng hơn.

Hàm Find() sẽ nhận vào 1 tham số index thể hiện cho số thứ tự của node đang được xét. Node được xét đầu tiên sẽ là node có số thứ tự 1. Hàm Find() sẽ thực hiện các thao tác sau:

  • Nếu như đoạn mà node đang được xét quản lí không chứa bất cứ một đoạn con nào của đoạn cần truy vấn (có nghĩa là low[index]>qj hoặc high[index]<qi) thì ta sẽ không tiếp tục xét nữa. Khi này, ta sẽ cần trả về một giá trị mà ta biết chắc không thể là kết quả để thể hiện việc node đó không được xét
  • Nếu như đoạn mà node đang được xét quản lí nằm hoàn toàn trong đoạn cần truy vấn (có nghĩa là qi\leq low[index] và high[index]<qj) thì ta sẽ trả về giá trị của node đang quản lí, chính là giá trị TNode[index]
  • Nếu như đoạn mà node đang được xét quản lí chứa một phần đoạn cần truy vấn, ta sẽ gọi đệ quy xuống hai nút con để tìm kiếm kết quả rồi trả về kết quả dựa theo kết quả hai nút con

Bản chất của toàn bộ quá trình truy vấn là chia đoạn cần truy vấn ra thành nhiều đoạn nhỏ và tìm kiếm kết quả trên các đoạn nhỏ đó.

Ở đây, mình sẽ xây dựng hàm Query() cho ví dụ ở đầu của chúng ta

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

class SegmentTree{

    int low[4 * MaxN], high[4 * MaxN], TNode[4 * MaxN], leaf[MaxN], qi, qj;

    int Find(int index){
        if(qi > high[index] || qj < low[index]) return 1e9;
        if(qi <= low[index] && high[index] <= qj) return TNode[index];
        return min(Find(index * 2), Find(index * 2 + 1));
    }

    public:
        void Build(int index, int l, int r){
            low[index] = l;
            high[index] = r;
            if(l == r){
                TNode[index] = a[l];
                leaf[l] = index;
                return;
            }
            Build(index * 2, l, (l + r) / 2);
            Build(index * 2 + 1, (l + r) / 2 + 1, r);
            TNode[index] = min(TNode[index * 2], TNode[index * 2 + 1]);
        } 

        int Query(int l, int r){
            qi = l;
            qj = r;
            return Find(1);
        }

} SegmentTree;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    SegmentTree.Build(1, 1, n);
    // Ta sẽ in ra kết quả ứng với dãy trong ví dụ của chúng ta
    cout << SegmentTree.Query(1, 5) << endl;
    // In ra kết quả: 2
    cout << SegmentTree.Query(4, 7) << endl;
    // In ra kết quả: 1

    return 0;
}

Hàm Update()

Hàm Update() là một hàm void nhận vào 2 tham số:

  • index: số thứ tự phần tử cần cập nhật
  • val: giá trị mới của phần tử cần cập nhật

Ta có một nhận xét như sau về quá trình cập nhật: Khi một node thay đổi thì chỉ giá trị của node cha của node đó thay đổi.

Do đó, quá trình cập nhật sẽ gồm các thao tác sau:

  • Lấy ra chỉ số của node lá thể hiện cho phần tử cần cập nhật
  • Cập nhật node lá đó
  • Cập nhật các node cha bị ảnh hưởng bởi sự thay đổi của node lá này. Do tính chất về số thứ tự ở trên nên nếu node con có số thứ tự là index thì node cha sẽ có số thứ tự là [\frac{index}{2}]. Do đó, các node được cập nhật sẽ có chỉ số là node, [\frac{index}{2}], [\frac{index}{4}], [\frac{index}{8}],_{\cdot \cdot \cdot }

Ở đây, mình sẽ xây dựng hàm Update() cho ví dụ ở đầu của chúng ta. Với việc xây dựng xong hàm Update() thì chương trình hoàn chỉnh cho bài toán ban đầu của chúng ta như sau:

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

class SegmentTree{

    int low[4 * MaxN], high[4 * MaxN], TNode[4 * MaxN], leaf[MaxN], qi, qj;

    int Find(int index){
        if(qi > high[index] || qj < low[index]) return 1e9;
        if(qi <= low[index] && high[index] <= qj) return TNode[index];
        return min(Find(index * 2), Find(index * 2 + 1));
    }

    public:
        void Build(int index, int l, int r){
            low[index] = l;
            high[index] = r;
            if(l == r){
                TNode[index] = a[l];
                leaf[l] = index;
                return;
            }
            Build(index * 2, l, (l + r) / 2);
            Build(index * 2 + 1, (l + r) / 2 + 1, r);
            TNode[index] = min(TNode[index * 2], TNode[index * 2 + 1]);
        } 

        int Query(int l, int r){
            qi = l;
            qj = r;
            return Find(1);
        }

        void Update(int index, int val){
            int pos = leaf[index];
            TNode[pos] = val;
            for(pos /= 2; pos > 0 ; pos /= 2) TNode[pos] = min(TNode[pos * 2], TNode[pos * 2 + 1]);
        }

} SegmentTree;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    SegmentTree.Build(1, 1, n);
    int q;
    cin >> q;
    while(q--){
        char query;
        int x, y;
        cin >> query >> x >> y;
        if(query == 'U') SegmentTree.Update(x, y);
        else cout << SegmentTree.Query(x, y) << endl;
    }

    return 0;
}

Độ phức tạp

Độ phức tạp của hàm Build() ở trên sẽ là n\times logn còn đối với các hàm Update() Query() sẽ có độ phức tạp là logn. Lí do là do độ sâu lớn nhất của một node trong cây nhị phân là n nên các thao tác với cây nhị phân đa phần sẽ chỉ mất độ phức tạp logn.


Mở rộng

Mình có một bài toán mở rộng như sau:

Cho một dãy gồm n số nguyên a_{i} (n\leq 10^{5}, |a_{i}| \leq 10^{9}). Có q truy vấn thuộc 1 trong 2 dạng sau:

  • U \ x \ y \ val: Tăng đoạn a_{x}, a_{x+1},_{\cdot \cdot \cdot }, a_{y} một giá trị  val(|val| \leq 10^{9})
  • Q \ u \ v: In ra giá trị nhỏ nhất trong đoạn a_{u}, a_{u+1},_{\cdot \cdot \cdot }, a_{v} \ (1 \leq u \leq v \leq n)

Ví dụ:

Input Output

7

3 5 2 6 9 1 2

6

Q 1 5

U 3 6 2

Q 1 5

U 2 5 -3

U 4 7 1

Q 2 6

2

3

-1

Giải thích ví dụ:

Ví dụ trên gồm có 6 truy vấn trong đó:

  • Truy vấn 1 yêu cầu in ra giá trị nhỏ nhất trong đoạn [1, 5] gồm các phần tử {3, 5, 2, 6, 9}. Do đó, giá trị nhỏ nhất trong đoạn này là 2. Ta in ra 2.
  • Truy vấn 2 tăng các phần tử trong đoạn [3, 6] thêm 1. Khi này, dãy đã cho trở thành 3, 5, 3, 7, 10, 1, 2.
  • Truy vấn 3 yêu cầu in ra giá trị nhỏ nhất trong đoạn [1, 5] gồm các phần tử {3, 5, 3, 7, 10}. Do đó, giá trị nhỏ nhất trong đoạn này là 3. Ta in ra 3.
  • Truy vấn 4 tăng các phần tử trong đoạn [2, 5] thêm -3. Khi này, dãy đã cho trở thành 3, 2, -1, 3, 6, 1, 2.
  • Truy vấn 5 tăng các phần tử trong đoạn [4, 7] thêm 1. Khi này, dãy đã cho trở thành 3, 2, -1, 4, 7, 2, 3.
  • Truy vấn 6 yêu cầu in ra giá trị nhỏ nhất trong đoạn [2, 6] gồm các phần tử {-1, 4, 7, 2}. Do đó, giá trị nhỏ nhất trong đoạn này là -1.

Cách làm cụ thể của bài này mình sẽ không trình bày trong khoá học này do nó tương đối phức tạp và khá khó. Tuy nhiên, nếu bạn nào có hứng thú với bài toán trên có thể tìm hiểu về “Lazy propagation”. Đây là một phương pháp khá thú vị trong tối ưu thời gian với Segment Tree.


Kết luận

  • Qua bài này chúng ta đã nắm được về Segment Tree
  • Bài sau chúng ta sẽ tìm hiểu về Fenwick Tree
  • Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.