- 首页 > 生活百科 > it技术 > >
lintcode-线段树查询I
/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
*int start, end, max;
*SegmentTreeNode *left, *right;
*SegmentTreeNode(int start, int end, int max) {
*this->start = start;
*this->end = end;
*this->max = max;
*this->left = this->right = NULL;
*}
* }
*/
#define INF 0x7fffffffclass Solution {
public:
/**
*@param root, start, end: The root of segment tree and
*an segment / interval
*@return: The maximum number in the interval [start, end]
*/int query(SegmentTreeNode *root, int start, int end) {
// write your code hereif(NULL == root) return -INF;
if(root->start > end || root->end < start || start > end) {
return -INF;
}if(root->start >= start && root->end <= end) return root->max;
int mid = (root->end + root->start)/2;
int leftmax = query(root->left, start, min(mid, end));
int rightmax = query(root->right, max(mid, start), end);
return max(leftmax, rightmax);
}
};
推荐阅读
