Cộng đồng công nghệ thông tin

Cây phân đoạn( Segment Tree) trong cấu trúc dữ liệu và giải thuật Đối tượng hướng đến : Các bạn đang học cấu trúc dữ liệu và giải thuật nâng cao Nội dung:     Trong các cuộc thi lập trình thuật toán, hay trong chương trình học ở trường, đôi khi chúng ta sẽ gặp những bài toán NHIỀU TRUY VẤN TRÊN CÙNG MỘT MẢNG, tiêu biểu nhất là bài toán cho một mảng gồm N số nguyên và M truy vấn. Trong M truy vấn đó mỗi truy vấn có dạng M x y, nghĩa là tìm số lớn nhất trong đoạn từ phần tử có chỉ số x đến phần tử có chỉ số y. Nếu chỉ dùng mảng một chiều đơn thuần để giải bài toán này thì cần rất nhiều thời gian cho việc truy xuất, độ phức tạp của thuật toán sẽ là O(N) cho mỗi truy xuất. Từ đó, người ta đã nghĩ ra một cấu trúc dữ liệu để tổ chức dữ liệu nhằm giải quyết nhanh gọn mấy bài toán chia khoảng kiểu này với độ phức tạp cho mỗi truy xuất là O(logN), và đó là cây phân đoạn( Segment Tree). Trên mạng đã có rất nhiều tài liệu hoặc bài viết nói về vấn đề này. Ở đây mình chỉ xin ...