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 3 năm trước 12.183 lượt xem 1 bình luận

Tác giả/Dịch giả:

huulam3011

Học nhanh

Danh sách bài học

Segment Tree

Nội dung bài viết Học nhanh

Dẫn nhập
Nội dung
Segment Tree
Kết luận
Tải xuống
- Tài liệu
Thảo luận

Bài trước Bài sau

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

3 5 2 6 9 1 2

Q 1 5

U 2 1

Q 1 5

U 6 4

U 7 9

Q 4 7

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ử a₂ 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ử a₆ thành 4 và a₇ 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

Độ 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()$ và $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

3 5 2 6 9 1 2

Q 1 5

U 3 6 2

Q 1 5

U 2 5 -3

U 4 7 1

Q 2 6

-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ó”.

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Segment Tree dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

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.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK

Nội dung bài viết

Dẫn nhập
Nội dung
Segment Tree
Kết luận
Tải xuống
- Tài liệu
Thảo luận

Tác giả/Dịch giả

huulam3011

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.

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa họ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 đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏ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

dat4444 đã bình luận 11 tháng trước

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í.

ai giải thích cho em tại sao cần kích thước 4 x MaxN với

Trả lời Báo cáo

Segment Tree

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

Danh sách bài học

Segment Tree

Segment Tree

Dẫn nhập

Nội dung

Bài toán đặt ra

Lời giải ban đầu

Nhận xét

Segment Tree

Khái niệm

Chuẩn bị

Cơ chế hoạt động

Hàm Build()

Hàm Query()

Hàm Update()

Độ phức tạp

Mở rộng

Kết luận

Tải xuống

Tài liệu

Thảo luận

Tác giả/Dịch giả

Khóa học

Đánh giá

Bình luận

Danh sách bài giảng

Không có video.

AD BLOCKER DETECTED