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 post code lên cho các bạn muốn dùng nó, chẳng hạn như dùng trong các project nhỏ trên trường, hoặc bài tập thầy cô giao. Ở đây mình đang tạo cây phân đoạn để tìm max và min trong từng đoạn cho trước.

Full source code và cách sử dụng có trong hàm main.
  1. #include<iostream>
  2. #include<vector>
  3. #include<math.h>
  4. #include<string>
  5. #include<algorithm>
  6. using namespace std;
  7. class Node
  8. {
  9. public:
  10. int max;
  11. int min;
  13. int leftBounder;
  14. int rightBounder;
  15. Node*leftNode;
  16. Node*rightNode;
  17. Node(int leftBounder = -1, int rightBounder = -1)
  18. {
  19. max = -2140000000;
  20. min = -max;
  21. this->leftBounder = leftBounder;
  22. this->rightBounder = rightBounder;
  23. leftNode = NULL;
  24. rightNode = NULL;
  25. }
  26. };
  27. class SegmentTree
  28. {
  29. private:
  30. Node*rootNode;
  31. void _build(Node*&root,vector<int>& vectorData)
  32. {
  33. if (root == NULL)
  34. {
  35. root = new Node(0,vectorData.size() - 1);
  36. _build(root, vectorData);
  37. }
  38. else
  39. {
  40. if (root->leftBounder == root->rightBounder)
  41. {
  42. root->max = root->min = vectorData[root->leftBounder];
  43. }
  44. if (root->leftBounder < root->rightBounder)
  45. {
  46. int mid = (root->leftBounder + root->rightBounder) / 2;
  47. root->leftNode = new Node(root->leftBounder, mid);
  48. root->rightNode = new Node(mid + 1, root->rightBounder);
  49. _build(root->leftNode, vectorData);
  50. _build(root->rightNode, vectorData);
  51. }
  52. }
  53. }
  54. void _clear(Node*&root)
  55. {
  56. if (root == NULL) return;
  57. _clear(root->rightNode);
  58. _clear(root->rightNode);
  59. delete root;
  60. root = NULL;
  61. }
  62. void _setMaxMin(Node*&root)
  63. {
  64. if (root == NULL) return;
  65. if (root->rightNode||root->leftNode) // both of two childs unequal NULL then root is not a leaf now
  66. {
  67. _setMaxMin(root->leftNode);
  68. _setMaxMin(root->rightNode);
  69. root->max = max(root->leftNode->max, root->rightNode->max);
  70. root->min = min(root->leftNode->min, root->rightNode->min);
  71. }
  72. }
  73. void _update(Node*&root, int index, int newValue)
  74. {
  75. if (root == NULL) return;
  76. if (!root->rightNode&&!root->leftNode) //then root is a leaf node
  77. {
  78. root->max = newValue;
  79. root->min = newValue;
  80. return;
  81. }
  82. if (index <= (root->leftBounder + root->rightBounder) / 2)
  83. {
  84. _update(root->leftNode, index, newValue);
  85. }
  86. else
  87. {
  88. _update(root->rightNode, index, newValue);
  89. }
  90. }
  91. int _getMax(Node*& root, int left, int right) //find max from left to right
  92. {
  93. if (left > right||root==NULL) return -2140000000;
  94. if (left == root->leftBounder&&right == root->rightBounder)
  95. {
  96. return root->max;
  97. }
  98. int mid = (root->leftBounder + root->rightBounder) / 2;
  99. if (left > mid)
  100. return _getMax(root->rightNode,left,right);
  101. if (right < mid)
  102. return _getMax(root->leftNode, left, right);
  103. int maxAtLeft = _getMax(root->leftNode, left, mid);
  104. int maxAtRight = _getMax(root->rightNode, mid+1, right);
  105. return max(maxAtLeft, maxAtRight);
  106. }
  107. int _getMin(Node*& root, int left, int right) //find min from left to right
  108. {
  109. if (left > right || root == NULL) return 2140000000;
  110. if (left == root->leftBounder&&right == root->rightBounder)
  111. {
  112. return root->min;
  113. }
  114. int mid = (root->leftBounder + root->rightBounder) / 2;
  115. if (left > mid)
  116. return _getMax(root->rightNode, left, right);
  117. if (right < mid)
  118. return _getMax(root->leftNode, left, right);
  119. int minAtLeft = _getMin(root->leftNode, left, mid);
  120. int minAtRight = _getMin(root->rightNode, mid + 1, right);
  121. return min(minAtLeft, minAtRight);
  122. }
  123. public:
  124. SegmentTree()//default constructor
  125. {
  126. //do nothing
  127. }
  128. SegmentTree(vector<int> vectorData)
  129. {
  130. _build(this->rootNode, vectorData);
  131. _setMaxMin(this->rootNode);
  132. }
  133. ~SegmentTree()
  134. {
  135. _clear(this->rootNode);
  136. }
  137. void build(vector<int> vectorData)
  138. {
  139. //clear all data befor build tree with new data
  140. _clear(this->rootNode);
  141. _build(this->rootNode, vectorData);
  142. _setMaxMin(this->rootNode);
  143. }
  144. void update(int index, int newValue)
  145. {
  146. _update(this->rootNode, index, newValue);
  147. _setMaxMin(this->rootNode);
  148. }
  149. int getMax(int left, int right) //find max from left to right
  150. {
  151. try
  152. {
  153. if (rootNode == NULL) throw "NULL POINTER EXCEPTION";
  154. if (left<0 || right>rootNode->rightBounder) throw "Query out of array";
  155. if (left > right) throw "Bad query, left index must be less than or equals right index";
  156. return _getMax(this->rootNode, left, right);
  157. }
  158. catch (char* exceptionMessage)
  159. {
  160. cout << exceptionMessage << endl;
  161. return -99999999;
  162. }
  163. }
  164. int getMin(int left, int right) //get min from left to right
  165. {
  166. try
  167. {
  168. if (rootNode == NULL) throw "NULL POINTER EXCEPTION";
  169. if (left<0 || right>rootNode->rightBounder) throw "Query out of array";
  170. if (left > right) throw "Bad query, left index must be less than or equals right index";
  171. return _getMin(this->rootNode, left, right);
  172. }
  173. catch (char* exceptionMessage)
  174. {
  175. cout << exceptionMessage << endl;
  176. return -99999999;
  177. }
  178. }
  179. };
  180. int main()
  181. {
  182. //my data
  183. vector<int> vectorData;
  184. vectorData.push_back(23);
  185. vectorData.push_back(2324);
  186. vectorData.push_back(56534);
  187. vectorData.push_back(4433);
  188. vectorData.push_back(2343);
  190. //build an Segment Tree base on above data
  191. SegmentTree segmentTree(vectorData);
  193. //then make a query on segment tree
  194. cout << segmentTree.getMin(0, 4) << endl;
  195. cout << segmentTree.getMax(0, 4) << endl;
  197. //try to update the tree
  198. segmentTree.update(2,11); //replace value at index = 2 by new value 11
  200. //then make a query on segment tree after updating
  201. cout << segmentTree.getMin(0, 4) << endl;
  202. cout << segmentTree.getMax(0, 4) << endl;
  203. return 0;
  204. }
Cây phân đoạn (Segment Tree) trong cấu trúc dữ liệu và giải thuật

Comments

Post a Comment

Popular posts from this blog

Duyệt cây nhị phân theo chiều rộng _Lập trình C++

Image
*) Đố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, biết cách sử dụng con trỏ, biết về stack, queue   - Các bạn khác đọc tham khảo *)Nội dung:     Có rất nhiều cách duyệt cây nhị phân, mỗi cách phù hợp với từng nhu cầu riêng của lập trình viên. Thường thì chúng ta duyệt theo chiều sâu (tức là duyệt LNR, LRN, NLR,...). Nhưng ít đề cập đến việc duyệt cây theo chiều rộng. Vậy nên mình sẽ chia sẻ với các bạn một phần nhỏ về kiến thức duyệt cây theo chiều rộng. - Đầu tiên cần biết duyệt cây theo chiều rộng tức là sẽ xuất các giá trị trên cây theo thứ tự từ trái qua phải và từ trên xuống dưới, xét cây sau: nếu xuất theo chiều rộng thì thứ tự xuất sẽ là: 40 5 45 35 56 15 48 13 16 47 49 Để làm được điều này chúng ta cần sư dụng một hàng đợi (queue), hàng đợi này lần lượt sẽ chứa các nút theo thứ tự trên, tức là chứa 40-> 5-> 45-> 35-> 56-> 15-> 48-> 13 ->16-> 47-> 49. Mà theo quy luật của hàng đợi, thì phần tử và...
Read more

Duyệt cây không dùng đệ quy và stack _Lập trình C++ căn bản

* )Giới thiệu: - Những thao tác trên cây thường rất đa dạng, mỗi loại thao tác lại có những phương thức và cách thao tác khác nhau. Thường thì người ta sẽ dùng đệ quy để tránh sự dài dòng, rắc rối. Chính vì đó, trong các tài liệu học tập trên trường học người ta ít đề cập đến việc thao tác với cây mà KHÔNG cần dùng đệ quy. Vậy hôm nay mình xin giới thiệu với các bạn cách duyệt cây nhị phân tìm kiếm theo kiểu InOrder(duyệt LNR) để minh họa.  Các kiểu duyệt khác (PreOrder, PostOrder,...) các bạn tự điều chỉnh lại cho phù hợp. *) Đối tượng hướng đến :  - Các bạn đang học lập trình C++, cấu trúc dữ liệu và giải thuật, có kiến thức vững chắc về con trỏ, cây nhị phân. *) Nội dung:  từ trước đến nay, khi tạo một cây thì chúng ta luôn thấy các nút lá có 2 con trỏ left và right là NULL(đây là dấu hiệu để nhận biết nó là nút lá(nói hơi thừa 😁😁😁😁)), ta sẽ lợi dụng các nút trống này để kết nối với các Node "tổ tiên" của nó. Những tác vụ này khiến các Node trên cây sẽ liên ...
Read more

Bài toán Upper Bound và Lower Bound trên cây nhị phân tìm kiếm

     Cây nhị phân tìm kiếm là một cấu trúc dữ liệu phổ biến được dùng để lưu trữ thông tin một cách có tổ chức, mọi thông tin trên cây đều tuân thủ quy luật nhất định, từ đó, việc quản lý và tìm kiếm dữ liệu được tối ưu hơn. Các thao tác trên cây thường rất đa dạng và đơn giản, nhưng không phải thao tác nào cũng đơn giản, ví dụ như thuật toán tìm Upper bound và Lower bound, nó đòi hỏi bạn phải biết cách dùng đệ quy khéo léo(à quên giới thiệu về Upper và lower bound, cứ hiểu đơn giản như sau,  Cho một dãy số, tìm trong dãy các số lower bound của x (số lớn nhất mà nhỏ hơn x) và upper bound của x (số nhỏ nhất mà lớn hơn x) ), để làm được bài này thì có rất nhiều cách, chẳng hạn sử dụng mảng để lưu trữ có sắp xếp, sau đó duyệt tuyến tính hoặc dùng BinarySearch để tìm kiếm, hoặc dùng danh sách liên kết đơn, kép, vòng,..tùy các bạn. Nhưng có lẽ tốt hơn hết là dùng cây nhị phân tìm kiếm,  việc thêm vào và tìm kiếm sẽ nhanh hơn nhiều. Giả sử bài toán được "biến tấu" ...
Read more