先看下线段树的介绍,下面这个链接讲得还不错 http://hi.baidu.com/semluhiigubbqvq/item/be736a33a8864789f4e4ad18
本文所讲的线段树和该文有微小区别,在该文中节点[0, 7]的左儿子为[0,3],右儿子为[4,7],不包含mid,而我们的线段树是包含的,即昨儿子为[0,3],右儿子为[3,7]。
现在我们用线段树解决以下问题(小米笔试题):
给定n个线段,每个线段告诉起点和终点,求线段总长度和,重合的部分只算一次。例如[0,3],[2,5],线段长度总和为[0,5]为5。实现代码如下:
#include <iostream> using namespace std; struct node { int left; int right; int cover; node() { cover = 0; } }; class LineSegmentTree { private: node *tree; public: LineSegmentTree() {}; LineSegmentTree(int left, int right); ~LineSegmentTree(); void init(int left, int right, int root); void insert(int left, int right, int root=1); int sum(int root=1); }; LineSegmentTree:: LineSegmentTree(int left, int right) { tree = new node[(right-left)*3](); init(left, right, 1); } void LineSegmentTree:: init(int left, int right, int root) { tree[root].left = left; tree[root].right = right; if(right - left == 1) { return; } int mid = (left + right) / 2; init(left, mid, 2*root); init(mid, right, 2*root+1); } void LineSegmentTree:: insert(int left, int right, int root) { if(right <= left) { return; } if(left == tree[root].left && right == tree[root].right) { tree[root].cover++; return; } int mid = (tree[root].right + tree[root].left) / 2; if(mid >= right) { insert(left, right, 2*root); } else if(mid <= left) { insert(left, right, 2*root+1); } else { insert(left, mid, 2*root); insert(mid, right, 2*root+1); } } int LineSegmentTree:: sum(int root) { if(tree[root].cover >= 1) { return tree[root].right - tree[root].left; } else if(tree[root].right - tree[root].left == 1) { return 0; } else { return sum(2*root) + sum(2*root+1); } } LineSegmentTree:: ~LineSegmentTree() { delete[] tree; } int main() { LineSegmentTree t(1, 15); t.insert(1, 4); t.insert(3, 5); t.insert(2, 6); t.insert(3, 5); t.insert(2, 3); t.insert(12, 13); t.insert(8, 13); cout<<t.sum()<<endl; return 0; }