线段树

 1 #ifndef _SEG_TREE_H_
 2 #define _SEG_TREE_H_
 3 
 4 #include <iostream>
 5 #include <cassert>
 6 #include <cstring>
 7 #include <iomanip>
 8 
 9 typedef struct seg_node
10 {
11     int left, right;
12     int mid;
13     int cover;//the segment is weather existed
14     /* some useful data*/
15     /* ....... */
16     seg_node():left(0),right(0),mid(0),cover(0){}
17 }seg_node;
18 class seg_tree
19 {
20 private:
21     seg_node *array;
22     int len;
23 
24     void _build(int left, int right, int index);
25     void _insert(int left, int right, int index);
26     bool _del(int left, int right, int index);
27 public:
28     seg_tree(int left, int right); // [left, right)
29     seg_tree(const seg_tree&);
30     seg_tree& operator = (const seg_tree&);
31     void insert(int left, int right);
32     bool del(int left, int right);
33 
34     friend void print_segtree(std::ostream& os, const seg_tree& st, int index, int depth);
35     friend bool operator == (const seg_tree& st1, const seg_tree& st2);
36 };
37 
38 void print_segtree(std::ostream& os, const seg_tree& st, int index = 0, int depth = 0);
39 bool operator == (const seg_tree& st1, const seg_tree& st2);
40 
41 #endif

  1 #include "./seg_tree.h"
  2 
  3 /***************************************
  4 * _build(int left, int right, int index)
  5 ***************************************/
  6 void seg_tree::_build(int left, int right, int index)
  7 {
  8     int mid = (left + right) / 2;
  9     array[index].left = left, array[index].right = right;
 10     array[index].mid = mid, array[index].cover = 0;
 11     if(left + 1 != right)
 12     {
 13         _build(left, mid, index*2+1);//insert left tree
 14         _build(mid, right, index*2+2);//insert right tree
 15     }
 16 }
 17 /***************************************
 18 * _insert(int left, int right, int index)
 19 ***************************************/
 20 void seg_tree::_insert(int left, int right, int index)
 21 {
 22     if(array[index].left == left && array[index].right == right)
 23     {
 24         array[index].cover = 1;
 25         return;
 26     }
 27     if(right <= array[index].mid)
 28         _insert(left, right, index*2+1);
 29     else if(left >= array[index].mid)
 30         _insert(left, right, index*2+2);
 31     else
 32     {
 33         _insert(left, array[index].mid, index*2+1);
 34         _insert(array[index].mid, right, index*2+2);
 35     }
 36 }
 37 /***************************************
 38 * _del(int left, int right, int index)
 39 ***************************************/
 40 bool seg_tree::_del(int left, int right, int index)
 41 {
 42     if(left >= right)
 43         return false;
 44     if(array[index].left + 1 == array[index].right)//leaf
 45     {
 46         int cover = array[index].cover;
 47         array[index].cover = 0;
 48         return cover;
 49     }
 50     if(array[index].cover)
 51     {
 52         array[index].cover = 0;
 53         array[index*2+1].cover = 1;
 54         array[index*2+2].cover = 1;
 55     }
 56     if(right <= array[index].mid)
 57         return _del(left, right, index*2+1);
 58     else if(left >= array[index].mid)
 59         return _del(left, right, index*2+2);
 60     else
 61         _del(left, array[index].mid, index*2+1) && 
 62         _del(array[index].mid, right, index*2+2);
 63 }
 64 /***************************************
 65 * seg_tree(int left, int right)
 66 ***************************************/
 67 seg_tree::seg_tree(int left, int right)
 68 {
 69     len = (right - left) * 3;
 70     array = new seg_node[len]();
 71     assert(array);
 72     _build(left, right, 0);
 73 }
 74 /***************************************
 75 * seg_tree(const seg_tree&)
 76 ***************************************/
 77 seg_tree::seg_tree(const seg_tree& st)
 78 {
 79     if(*this == st)
 80         return;
 81     len = st.len;
 82     delete[] array;
 83     array = new seg_node[len];
 84     assert(array);
 85     memcpy(array, st.array, sizeof(seg_node)*len);    
 86 }
 87 /***************************************
 88 * operator = (const seg_tree&)
 89 ***************************************/
 90 seg_tree& seg_tree::operator = (const seg_tree& st)
 91 {
 92     if(*this == st)
 93         return *this;
 94     len = st.len;
 95     delete[] array;
 96     array = new seg_node[len];
 97     assert(array);
 98     memcpy(array, st.array, sizeof(seg_node)*len);
 99 }
100 /***************************************
101 * insert(int left, int right)
102 ***************************************/
103 void seg_tree::insert(int left, int right)
104 {
105     _insert(left, right, 0);
106 }
107 /***************************************
108 * del(int left, int right)
109 ***************************************/
110 bool seg_tree::del(int left, int right)
111 {
112     return _del(left, right, 0);
113 }
114 
115 /***************************************
116 * print_segtree(std::ostream& os, const seg_tree& st, int index, int depth)
117 ***************************************/
118 void print_segtree(std::ostream& os, const seg_tree& st, int index/*=0*/, int depth/*=0*/)
119 {
120     if(    !os 
121         || st.array[index].left >= st.array[index].right 
122         || st.array[index].left < st.array[0].left
123         || st.array[index].right > st.array[0].right)
124         return;
125     print_segtree(os, st, index*2+1, depth+5);
126     os<<std::setw(depth)<<"["<<st.array[index].left<<" ,"<<st.array[index].right<<")"
127     <<":"<<(st.array[index].cover?"existed":"")<<std::endl;
128     print_segtree(os, st, index*2+2, depth+5);
129 }
130 /***************************************
131 * operator == (const seg_tree& st1, const seg_tree& st2)
132 ***************************************/
133 bool operator == (const seg_tree& st1, const seg_tree& st2)
134 {
135     if(st1.len != st2.len)
136         return false;
137     return memcmp(st1.array, st2.array, st1.len*sizeof(seg_node)) == 0;
138 }

下面是测试代码

 1 #include "./seg_tree.h"
 2 #include <iostream>
 3 using namespace std;
 4 
 5 int main(int argc, char const *argv[])
 6 {
 7     seg_tree st(1,10);
 8     print_segtree(cout, st);
 9     cout<<endl;cout<<endl;
10     st.insert(3,10);
11     print_segtree(cout, st);
12     cout<<endl;cout<<endl;
13     st.del(3,10);
14     print_segtree(cout, st);
15     return 0;
16 }

首先生成一棵范围在[1, 10)之间的树

然后添加线段[3, 10)之后会在线段后面显示"existed"，最后我们又把这条线段删除之