给定一个整数数组（下标由 0 到 n-1， n 表示数组的规模，取值范围由 0 到10000）。对于数组中的每个 ai 元素，请计算 ai 前的数中比它小的元素的数量。
注意事项
We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number first.
样例
对于数组[1,2,7,8,5] ，返回 [0,1,2,3,2]
解题思路：
题目提示我们使用线段树，在这里我写了两种线段树的解法，一种TLE，一种正常通过；个人感觉两种写法需要因地制宜使用：
思路1：每个线段树节点存储的是原始vector的index前后值以及该区间内的相应最大值，在查询时，通过区域以及最大值约束找到所有小于特定值的区间最后求和。
class SegmentTreeNode{ //线段树节点，其中max是当前区域内（left-right）最大值
public:int start,end,max;SegmentTreeNode2 * left;SegmentTreeNode2 * right;SegmentTreeNode2(int x,int y,int max){this->start = x;this->end = y;this->max = max;this->left = this->right = nullptr;}
};class Solution {
public:/*** @param A: an integer array* @return: A list of integers includes the index of the first number and the index of the last number*/vector<int> countOfSmallerNumberII(vector<int> &A) {// write your code hereauto tree = new SegmentTreeNode(0,A.size()-1,INT_MIN);buildTree(A,tree);vector<int> ret;for(int i = 0;i<A.size();++i){ret.push_back(query(tree,0,i,A[i]));}return ret;}int buildTree(vector<int> &A,SegmentTreeNode * root){ //建立线段树，每个节点保存该区域内最大值int start = root->start;int end = root->end;if(start > end) return 0;if(start == end) {root->max = A[start];return A[start];}else{root->left = new SegmentTreeNode(start,(start+end)/2,INT_MIN);root->right = new SegmentTreeNode((start+end)/2+1,end,INT_MIN);int L_max = buildTree(A,root->left);int R_max = buildTree(A,root->right);root->max = L_max>R_max?L_max:R_max;return root->max;};}int query(SegmentTreeNode * root,int start,int end,int q){ //查询特定区域比q小的个数if(root == nullptr) return 0;if(root->start > end || root->end < start) return 0;if(root->start >= start && root->end <= end && root->max<q) return root->end - root->start + 1;return query(root->left,start,end,q)+query(root->right,start,end,q);}
};
这种解法TLE，时间复杂度在vector的size很大时很大，某种程度上来讲效率不及直接暴力法，但当所求数据较为集中时应该能提高一点速度。
思路2：对数据的区间建立线段树，在知道所有数据上界的情况下效率不错，能够正常通过
class SegmentTreeNode{//count表示当前区间所有的数个数
public:int start,end,count;SegmentTreeNode * left;SegmentTreeNode * right;SegmentTreeNode(int x,int y,int count){this->start = x;this->end = y;this->count = count;this->left = this->right = nullptr;}
};class Solution {
public:/*** @param A: an integer array* @return: A list of integers includes the index of the first number and the index of the last number*/vector<int> countOfSmallerNumberII(vector<int> &A) {// write your code herevector<int> res;SegmentTreeNode * root = buildTree(0,10001);for(int i=0; i<A.size(); ++i){res.push_back(query(root,A[i]));insert(root,A[i]);}return res;}SegmentTreeNode* buildTree(int start,int end){ //这种方法需要明确数据上界，然后直接根据数据大小建立线段树，每个节点保存落在当前区间数的个数if(start > end) return nullptr;auto res = new SegmentTreeNode(start,end,0);if(start == end) return res;int mid = (start+end)/2;res->left = buildTree(start,mid);res->right = buildTree(mid+1,end);return res;}int query(SegmentTreeNode * root,int q){ //query函数用来查询当前区域内小于q的数的个数if(root == nullptr) return 0;if(q < root->start) return 0;if(q > root->end) return root->count;return query(root->left,q)+query(root->right,q);}void insert(SegmentTreeNode * root,int val){//将输入数据逐个插入，从上到下逐个更新countif(root == nullptr) return;if(root->start > val || root->end < val) return;if(root->start <= val && root->end >= val) ++root->count;insert(root->left,val);insert(root->right,val);}
}
ps:这道题如果使用lintcode内置的SegmentTreeNode 数据结构中的count好像会出问题，最好定义自己的class
