本文主要是介绍LeetCode 题247：线段树的查询（2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
对于一个数组，我们可以对其建立一棵线段树, 每个结点存储一个额外的值 count 来代表这个结点所指代的数组区间内的元素个数。(数组中并不一定每个位置上都有元素)
实现一个 query 的方法，该方法接受三个参数 root, start 和end, 分别代表线段树的根节点和需要查询的区间，找到数组中在区间[start, end]内的元素个数。
例如：
对于数组 [0, 空，2, 3], 对应的线段树为：
query(root, 1, 1), return 0
query(root, 1, 2), return 1
query(root, 2, 3), return 2
query(root, 0, 2), return 2
数据结构：
/*** 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:int query(SegmentTreeNode *root, int start, int end){if(root == NULL || start > end){return 0;}if(root->start > end || root->end < start){return 0;}if(root->start >= start && root->end <= end){return root->count;}int mid = root->start + (root->end - root->start)/2; if(start > mid) {return query(root->right,start,end); }else if(end < mid+1){return query(root->left,start,end); }else {return query(root->left,start,mid) + query(root->right,mid+1,end); }}
};
这篇关于LeetCode 题247：线段树的查询（2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
