/**
* Definition of SegmentTreeNode:
* class SegmentTreeNode {
* public:
* int start, end, count;
* SegmentTreeNode *left, *right;
* SegmentTreeNode(int start, int end, int count) {
* this->start = start;
* this->end = end;
* this->count = count;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The count number in the interval [start, end]
*/
int query(SegmentTreeNode *root, int start, int end) {
// write your code here
if(root == NULL) { return 0; }
if(start > end || start > root->end || end < root->start) { return 0; }
if(start <= root->start && end >= root->end) { return root->count; }
int mid = (root->start + root->end) / 2;
int left = query(root->left, start, min(mid, end));
int right = query(root->right, max(mid, start), end);
return left+right;
}
};
lintcode-Segment Tree Query II
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 原题 对于一个数组，我们可以对其建立一棵线段树, 每个结点存储一个额外的值count来代表这个结点所指代的数组区间...
- 原题 LintCode 70. Binary Tree Level Order Traversal II Desc...
- 原题 对于一个有n个数的整数数组，在对应的线段树中, 根节点所代表的区间为0-n-1, 每个节点有一个额外的属性m...
- 【题目描述】 For an array, we can build a Segment Tree for it, ...
