/**
* 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 0x7fffffff
class 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 here
if(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);
}
};
lintcode-线段树查询I
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 线段树(又称区间树), 是一种高级数据结构，他可以支持这样的一些操作: 查找给定的点包含在了哪些区间内 查找给定的...
- 2014年09月23日 9695 愿你纵深一跃，不惧深渊。愿风暴降临，你岸堤永固。愿人群声嘶力竭，呼喊你名。愿众人...
- 本篇文章是继续上篇android图片压缩上传系列－基础篇文章的续篇。主要目的是：通过Service来执行图片压缩任...
