Học về Segment Tree

Segment Tree được sử dụng trong trường hợp có nhiều truy vấn phạm vấn phạm vi trên mảng và sửa đổi các phần tử của cùng một mảng. Ví dụ, tìm tổng của tất cả các phần tử trong một mảng từ chỉ số L đến R, hoặc tìm giá trị nhỏ nhất của tất cả các phần tử trong 1 mảng từ chỉ số L đến R. Những vấn đề này có thể được giải quyết dễ dàng với một trong những cấu trúc dữ liệu linh hoạt nhất. Segment Tree.

Segment Tree là gì ?
Segment Tree cơ bản là một cây nhị phân nhằm lưu trữ một đoạn. Mỗi nút trong Segment Tree đại diện cho một đoạn. Xét mảng A có kích thước N, và 1 cây Segment Tree T tương ứng.

1. Gốc của cây T sẽ đại diện cho cả mảng: A[0:N-1].
2. Mỗi lá của cây T sẽ đại diện một phần tử A[i] thỏa mãn 0<=i<N.
3. Mỗi nút nút của cây T đại diện cho một đoạn A[i:j] với 0<=i<j<N.

Gốc của Segment Tree đại diện cho cả mảng A[0:N-1]. Sau đó nó chia đôi thành một nữa và 2 đứa trẻ của gốc sẽ đại diện cho A[0:(N-1)/2]  và A[(N-1)/2+1;(N-1)]. Vì vậy, ở mỗi bước, Segment lại chia làm đôi và 2 đứa trẻ đại diện cho 1 nửa của chúng. Số nút internal là N-1. Do đó số nút tổng cộng là 2*N-1.

Khi Segment Tree được dựng, cấu trúc của nó sẽ không bị thay đổi. Chúng ta có thể update giá trị của nút nhưng không thay đổi cấu trúc của nó. Segment Tree chia thành 2 phép toán sau:
1. Update. Để update 1 phần tử trên mảng A và phản chiếu sự thay đổi tương ứng trong Segment Tree.
2. Truy vấn. Trong phép toán này, chúng ta có thể truy vấn trên 1 đoạn và trả lại đáp án cho bài toán (có thể là tổng, giá trị lớn nhất, giá trị nhỏ nhất trong 1 đoạn cụ thể).

Triển khai:
+ Bởi vì Segment Tree là cây nhị phân, một mảng tuyến tính đơn giản có thể được sử dụng để sử dụng để biểu diễn Cây phân đoạn. Trước khi xây dựng 1 Segment Tree, người ta cần phải tìm ra những gì cần được lưu trữ trong nút của Segment Tree.
Ví dụ, nếu câu hỏi là tìm tổng của tất cả các phần tử của một mảng từ chỉ số L đến chỉ số R, thì mỗi nút (ngoại trừ nút lá), tổng của các nút con sẽ được lưu.

Segment Tree có thể được xây dựng bằng cách sử dụng đệ quy (tiếp cận theo hướng bottom-up). Bắt đầu với nút lá và đi đến gốc và cập nhật những thay đổi tương ứng ở các nút trên đường đi từ lá đến gốc. Lá đại diện cho một phần tử đơn. Mỗi bước, dữ liệu của hai nút con được sử dụng để tạo thành 1 nút cha. Mỗi nút sẽ đại diện cho sự kết tinh của những nút con hợp lại. Kết hợp khác nhau sẽ cho ra những câu hỏi khác nhau. Vì vậy đệ quy sẽ kết thúc tại nút và đại diện cho toàn mảng.

Đối với update(), tìm kiếm nút lá chứa phần tử cần update. Điều này có thể được thực hiện bằng cách đi đến con bên trái hoặc con bên phải tùy thuộc vào đoạn chứa phần tử đó. Khi lá được tìm thấy, nó được cập nhật và một lần nữa sử dụng cách tiếp cận bottum-up để cập nhật những thay đổi tương ứng trên đường từ lá đến gốc.

Để làm 1 query() trên Segment Tree, ta chọn 1 đoạn từ L đến R (thường được dùng cho câu hỏi). Đệ quy trên cây bắt đầu từ gốc và kiểm tra liệu rằng nếu đoạn đó được đại diện bởi nút hoàn toàn trong đoạn L đến R. Nếu được được biểu diễn bởi một nút hoàn toàn trong dãy từ L đến R, chúng ta trả lại giá trị của node.

Segment Tree của mảng A có kích thước 7 sẽ như sau:

Ta lấy một ví dụ, Cho một mảng A có kích thước N và một vài truy vấn. Có 2 loại truy vấn sau:

1. Update: Cho idx và val, cập nhật phần tử mảng A[idx]=A[idx]+val

2. Query : Cho l và r , trả lại giá trị của A[l]+A[l+1]+A[l+2]+...+A[r-1]+A[r] thỏa mãn 0<=l<=r<N.

Queries và Updates có thể bất kì vị trí nào.

Thuật toán Trâu bò:

+ Đây là hướng tiếp cận đơn giản nhất. Đối với mỗi truy vấn, chạy 1 vòng từ l đến r và tính tổng của tất cả các phần tử. Vì vậy mỗi truy vấn sẽ tốn O(N).

+ A[idx]+=val sẽ cập nhật giá trị của phần tử. Mỗi update sẽ tốn O(1).

Thuật toán này tốt nếu số lượng queries rất thấp so với update trong mảng.

Sử dụng Segment Tree.

Đầu tiên, chỉ ra điều gì cần được lưu trữ trong mỗi nút của cây Segment tree. Câu hỏi yêu cầu tổng các phần tử trong đoạn từ l đến r, vì vậy mỗi nút, tổng của tất cả các phần tử ở trong đoạn này được đại diện bởi nút. Tiếp theo, ta xây dựng Segment Tree. Việc triển khai với những comment dưới đây giải thích quá trình xây dựng sau:

```

void build(int node, int start, int end)
{
    if(start == end)
    {
        // Leaf node will have a single element
        tree[node] = A[start];
    }
    else
    {
        int mid = (start + end) / 2;
        // Recurse on the left child
        build(2*node, start, mid);
        // Recurse on the right child
        build(2*node+1, mid+1, end);
        // Internal node will have the sum of both of its children
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

```

Như đoạn code ở trên, bắt đầu từ nút gốc và đệ quy bên trái, bên phải  đến khi chạm đến nút lá. Từ những lá, quy lại gốc và update tất cả những nút trên đường. Node đại diện cho nút hiện tại đang được xử lý. Bởi vì Segment Tree là cây nhị phân. 2*node sẽ đại diện cho nút bên trái và 2*node+1 sẽ đại diện cho nút bên phải. start và end đại diện cho đoạn bởi nút. Độ phức tạp của việc build là O(N).

Để update 1 phần tử, nhìn vào đoạn nơi mà các phần tử hiện tại và đệ quy theo con bên trái hoặc bên phải.

```

void update(int node, int start, int end, int idx, int val)
{
    if(start == end)
    {
        // Leaf node
        A[idx] += val;
        tree[node] += val;
    }
    else
    {
        int mid = (start + end) / 2;
        if(start <= idx and idx <= mid)
        {
            // If idx is in the left child, recurse on the left child
            update(2*node, start, mid, idx, val);
        }
        else
        {
            // if idx is in the right child, recurse on the right child
            update(2*node+1, mid+1, end, idx, val);
        }
        // Internal node will have the sum of both of its children
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}

```

Độ phức tạp của việc update là O(logN).

Để truy vấn trong một dãy được cho, cần kiểm tra 3 điều kiện:

1. Dãy được cho bỏi 1 nút cho hoàn toàn nằm trong dãy đã cho hay không

2. Dãy được cho bởi 2 nút có nằm hoàn toàn nằm ngoài dãy đã cho hay không

3. Dãy đươch cho bởi 1 nút 1 một phần nằm ở trong và 1 phần nằm ở ngoài dãy đã cho hay không.

Nếu dãy đã cho bởi một nút hoàn toàn nằm ngoài dãy đã cho, đơn giản trả về 0. Nếu dãy đã cho bởi một nút nằm trong dãy đã cho, trả lại giá trị của nút  đó chính là tổng của các phần tử trong dãy bỏi nút. Và nếu một dãy được cho bởi một nút một phần nằm trong và một phần nằm ngoài của dãy đã cho, trả lại tổng cây trái và cấy phải. Độ phức tạp của query này sẽ là O(logN).

```

int query(int node, int start, int end, int l, int r)
{
    if(r < start or end < l)
    {
        // range represented by a node is completely outside the given range
        return 0;
    }
    if(l <= start and end <= r)
    {
        // range represented by a node is completely inside the given range
        return tree[node];
    }
    // range represented by a node is partially inside and partially outside the given range
    int mid = (start + end) / 2;
    int p1 = query(2*node, start, mid, l, r);
    int p2 = query(2*node+1, mid+1, end, l, r);
    return (p1 + p2);
}

```