Cho dãy A gồm N phần tử số nguyên có giá trị a1 a2 aN hãy sắp xếp dãy A theo chiều không giảm

LƯU Ý:

• Khi Segment Tree mới được du nhập vào Việt Nam, một số tài liệu gọi là Interval Tree. Đây là cách gọi không chính xác, bởi Interval Tree là một CTDL khác.
• Tất cả hàm trong bài đều đánh số từ 1. Các nút của cây phân đoạn sẽ quản lý đoạn $[l,r]$
• Segment Tree còn có một cách cài đặt khác sử dụng ít bộ nhớ hơn [tối đa $2*N$ phần tử], cài đặt ngắn hơn và chạy nhanh hơn. Tuy nhiên theo cá nhân mình không dễ hiểu bằng cách cài đặt trong bài viết này.

0. Giới thiệu

Segment Tree là một cấu trúc dữ liệu được sử dụng rất nhiều trong các kỳ thi, đặc biệt là trong những bài toán xử lý trên dãy số.

Segment Tree là một cây. Cụ thể hơn, nó là một cây nhị phân đầy đủ [mỗi nút là lá hoặc có đúng 2 nút con], với mỗi nút quản lý một đoạn trên dãy số. Với một dãy số gồm $N$ phần tử, nút gốc sẽ lưu thông tin về đoạn $[1, N]$, nút con trái của nó sẽ lưu thông tin về đoạn $[1, ⌊N/2⌋]$ và nút con phải sẽ lưu thông tin về đoạn $[⌊N/2⌋+1, N]$. Tổng quát hơn: nếu nút $A$ lưu thông tin đoạn $[i, j]$, thì 2 con của nó: $A1$ và $A2$ sẽ lưu thông tin của các đoạn $[i, ⌊[i+j]/2⌋]$ và đoạn $[⌊[i+j]/2⌋ + 1, j]$.

Ví dụ

Xét một dãy gồm 7 phần tử, Segment Tree sẽ quản lý các đoạn như sau:

Cài đặt

Để cài đặt, ta có thể dùng một mảng 1 chiều, phần tử thứ nhất của mảng thể hiện nút gốc. Phần tử thứ $id$ sẽ có 2 con là $2 * id$ [con trái] và $2 * id+1$ [con phải]. Với cách cài đặt này, người ta đã chứng minh được bộ nhớ cần dùng cho ST không quá $4 * N$ phần tử.

Áp dụng

Để dễ hình dung, ta lấy 1 ví dụ cụ thể:

• Cho dãy $N$ phần tử $[N \le 10^5]$. Ban đầu mỗi phần tử có giả trị 0.
• Có $Q$ truy vấn $[Q \le 10^5]$. Mỗi truy vấn có 1 trong 2 loại:
  1. Gán giá trị $v$ cho phần tử ở vị trí $i$.
  2. Tìm giá trị lớn nhất cho đoạn $[i, j]$.

Cách đơn giản nhất là dùng 1 mảng $A$ duy trì giá trị các phần tử. Với thao tác 1 thì ta gán $A[i] = v$. Với thao tác 2 thì ta dùng 1 vòng lặp từ $i$ đến $j$ để tìm giá trị lớn nhất. Rõ ràng cách này có độ phức tạp là $O[N*Q]$ và không thể chạy trong thời gian cho phép.

Cách dùng Segment Tree như sau:

• Với truy vấn loại 1, ta sẽ cập nhật thông tin của các nút trên cây ST mà đoạn nó quản lý chứa phần tử $i$.
• Với truy vấn loại 2, ta sẽ tìm tất cả các nút trên cây ST mà đoạn nó quản lý nằm trong $[i, j]$, rồi lấy max của các nút này.

Cài đặt như sau: