# Segment Tree :: Part 1
***Writer**: Nguyễn Hữu Phúc*
***Reviewer**: Founding...*
> **Segment Tree** là một cấu trúc dữ liệu mạnh trong lập trình thi đấu với thời gian chạy thấp, dựa vào đó ta có thể sử dụng các kĩ thuật từ cơ bản tới phức tạp với độ hiệu quả cao.
### I. Giới thiệu cơ bản về Segment Tree
Về cơ bản, Segment Tree là một tập hợp dữ liệu quản lí các phần tử trong tập hợp dưới dạng một **cây nhị phân**, có nghĩa là, một đỉnh cha sẽ quản lí hai đỉnh con, đỉnh con dưới cùng (hay còn gọi là lá) sẽ chính là một phần tử trong tập hợp cần quản lí.
*Ví dụ minh họa cho cây quản lí một tập hợp có 4 phần tử*
### II. Phân tích Segment Tree
#### 1. Lưu trữ cây
* Câu hỏi đầu tiên được đặt ra đó chính là: Chúng ta sẽ lưu trữ cây bằng cách nào, đáp án cho câu hỏi này chính là bằng **một mảng có kích thước bằng 4 lần kích cỡ mảng cần quản lí**.
> Nếu đến đây các bạn nói là chỉ cần một mảng $2n$ thôi thì lí do mình dùng mảng $4n$ là vì ~~mình thích~~ nó dễ hiểu và dễ cài đặt hơn, thời gian chạy thì không chênh lệch nhiều lắm
Lí do của việc này đó chính là: Gọi n là kích thước của mảng thì cây sẽ có $log n$ tầng, tầng đầu tiên của cây có $n$ phần tử, tầng thứ 2 có $\dfrac {n}{2}$ phần tử, tầng thứ 3 có $\dfrac {n}{4}$ phần tử,... Từ đó, ta có thể chứng minh được số phần tử sẽ không quá $4n$ (phần chứng minh xin được nhường lại cho bạn đọc).
#### 2. Phân tích thời gian truy vấn
* Câu hỏi thứ hai được đặt ra chính là: Tại sao với mỗi truy vấn (**xin nhấn mạnh là cơ bản chứ không phải mấy cái thuật khủng bố mà mọi người hay dùng**) thì chỉ tốn $O(log n)$ thời gian, đáp án cho câu hỏi này đó chính là: Thời gian truy vấn sẽ đúng bằng chiều cao của cây.
Lí do cho việc này chính là cấu trúc của cấu trúc dữ liệu này, một đỉnh cha sẽ có $2$ đỉnh con và một đỉnh con sẽ chỉ có $1$ đỉnh cha duy nhất nên khi cập nhật một đỉnh con, nó sẽ cập nhật đỉnh cha của nó, rồi cứ như vậy cập nhật tới đỉnh nguồn, và từ đó ta thấy số tầng của cây (chính bằng `$O(logn)$).
#### 3. Xây dựng Segment Tree
Vậy, để xây dựng một Segment Tree, chúng ta sẽ làm như thế nào, sau đây là mã giả của hàm $Build$ mà mình hay dùng:
```cpp
Build (id, l, r){
if (l == r){
tree[id] = {a[l]};
return;
}
m = (l + r) / 2;
Build(id * 2, l, m);
Build(id * 2 + 1, m + 1, r);
tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
// với merge là thao tác cần quản lí như lấy tổng, xor, gcd,...
}
```
Để bạn đọc dễ hình dung thì đỉnh $id$ sẽ quản lí đoạn từ $l$ tới $r$ hay nói cách khác nó sẽ quản lí đỉnh $id * 2$ (quản lí từ $l$ tới $m$) và $id * 2 + 1$ (quản lí từ $m + 1$ tới $r$) với $m$ là trung điểm của đoạn $l - r$.
Lí do của việc quản lí như thế này chính là, nếu như sắp xếp các đỉnh quản lí phần tử $1, 2, 3, ...$ theo thứ tự thì rất khó để xây dựng cây kiểm soát các phần tử này (hoặc là tại mình ngoo không biết cách xây như vậy).
#### 4. Cập nhật Segment Tree
Tương tự với cách $Build$ ta cũng có thể cập nhật một phần tử $k$ thành giá trị $x$ trong đoạn như sau:
```cpp
Update (id, l, r, k, x){
if (l > k || r < k) return;
// nếu l > k hoặc r < k thì ta có thể thấy nó không quản lí k, do vậy không cần cập nhật
if (l == r){
tree[id] = x;
return;
}
// nếu l = r thì ta có thể thấy l = k, r = k
// => tree[id] chính là lá quản lí phần tử k
// => cập nhật tree[id] = x;
int m = (l + r) / 2;
Update(id * 2, l, m, k, x);
Update(id * 2 + 1, m + 1, r, k, x);
// đoạn này tương tự đoạn Build ở trên nên mình sẽ không đề cập thêm
}
```
#### 5. Lấy kết quả trên đoạn bằng Segment Tree
Và cuối cùng, chính là hàm $Get$ lấy giá trị trong một đoạn $l$ - $r$. Cách làm tương tự như hai cái trên, chỉ khác một chỗ chính là truy vấn độ cao của chúng.
Trước tiên, hãy nói về cách hoạt động, một đoạn $l$ - $r$ có thể không có một đỉnh nào quản lí vì nó chỉ có các đỉnh quản lí độ dài $1$, $2$, $4$,... Vậy thì làm thế nào để tìm giá trị trong khoảng $l$ - $r$ với $O(logn)$.
Chúng ta có thể lấy cách làm tham lam cho truy vấn trên, cụ thể như sau:
Nếu như đỉnh $id$ quản lí một đoạn nằm trong $l$ - $r$ thì chúng ta lấy luôn đỉnh đó và thực hiện thao tác $merge$ tương tự với các đỉnh con khác mà ta lấy.
Lí do của việc này là vì, nếu như ta lấy đỉnh con $id$ thì sau đó các đỉnh con của đỉnh $id$ sẽ không được lấy nữa và từ đó ta có thể chứng minh được không lấy một phần tử nào quá hai lần.
Ví dụ nhé, chúng ta có một truy vấn là $2$ - $4$ trên một đoạn gồm 4 phần tử.
Theo cách làm trên của mình, ta sẽ từ từ di chuyển từ các đỉnh cha xuống đỉnh con, nếu đỉnh con nằm hoàn toàn trong $l$ - $r$ thì lấy đỉnh con đó luôn và kết thúc di chuyển ở đỉnh con đó.
* Bắt đầu từ đỉnh $1$ quản lí $1$ - $4$.
* Vì đoạn $1$ - $4$ không nằm trong $2$ - $4$ nên di chuyển xuống tới hai đỉnh lần lượt là $1$ - $2$ và $3$ - $4$.
* Đỉnh $1$ - $2$ vẫn tiếp tục không nằm trong đoạn nên di chuyển xuống hai đỉnh $1$ - $1$ và $2$ - $2$. Đỉnh $3$ - $4$ nằm hoàn toàn trong đoạn rồi nên ta thực hiện thao tác $merge$ giữa nó và kết quả của các đỉnh con khác.
* Đỉnh $1$ - $1$ không hợp lệ nhưng đỉnh $2$ - $2$ thì có nên ta $merge$ nó với kết quả của các đỉnh con khác mà lúc này ta thấy là đỉnh $3$ - $4$.
* $2$ - $2$ $merge$ $3$ - $4$ thì kết quả sẽ là $2$ - $4$ chính là kết quả mà ta tìm kiếm.
Từ các bước minh họa trên, mình tin là các bạn đã hiểu cách hoạt động của hàm $Get$ rồi, bây giờ chúng ta sẽ code đoạn này như sau:
```cpp
Get (id, l, r, u, v){
if (l > v || r < u) return startvalue;
// nếu l > v hoặc r < u thì lúc này nó chắc chắn sẽ không nằm trong đoạn nữa
// => ta return luôn tránh chạy lãng phí thời gian
if (l >= u && r <= v) return tree[id];
// nếu nằm trong đoạn thì return luôn như mình nói
int m = (l + r) / 2;
return merge(Get(id * 2, l, m, u, v), Get(id * 2, m + 1, r, u, v));
// trả về merge của kết quả các đỉnh con
}
```
Giải thích một chút, $startvalue$ trong đoạn code trên chính là giá trị ảo sao cho nó không làm chương trình chạy sai, ví dụ khi lấy tổng, ta đặt $startvalue$ là $0$, khi lấy $gcd$ cũng là $0$, $max$ thì lấy $INF$ với $INF$ là một số nhỏ hơn các giá trị trong đoạn (với mình thì mình thường lấy là $-INF$ với $INF$ là $10^{16}$).
### III. Đoạn kết
Ok, giải thích sơ qua về các hàm như vậy là đủ cho part 1 này rồi, cảm ơn các bạn đã đọc tới đây, nếu có sai sót gì thì cứ nói nhé. Cảm ơn các bạn rất nhiều.
### IV. Bài tập ví dụ
> [ITEZ 1 - VNOJ](https://oj.vnoi.info/problem/segtree_itez1)
> [ITEZ 2 - VNOJ](https://oj.vnoi.info/problem/segtree_itez2)
Sign in with Wallet
Connect another wallet