LeetCode 题247:线段树的查询(2)

2024-08-24 09:08
文章标签 leetcode 查询 线段 247

本文主要是介绍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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102047

相关文章

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

MYSQL查询结果实现发送给客户端

《MYSQL查询结果实现发送给客户端》:本文主要介绍MYSQL查询结果实现发送给客户端方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql取数据和发数据的流程(边读边发)Sending to clientSending DataLRU(Least Rec

MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)

《MySQL复杂SQL之多表联查/子查询详细介绍(最新整理)》掌握多表联查(INNERJOIN,LEFTJOIN,RIGHTJOIN,FULLJOIN)和子查询(标量、列、行、表子查询、相关/非相关、... 目录第一部分:多表联查 (JOIN Operations)1. 连接的类型 (JOIN Types)

python编写朋克风格的天气查询程序

《python编写朋克风格的天气查询程序》这篇文章主要为大家详细介绍了一个基于Python的桌面应用程序,使用了tkinter库来创建图形用户界面并通过requests库调用Open-MeteoAPI... 目录工具介绍工具使用说明python脚本内容如何运行脚本工具介绍这个天气查询工具是一个基于 Pyt

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

在Java中基于Geotools对PostGIS数据库的空间查询实践教程

《在Java中基于Geotools对PostGIS数据库的空间查询实践教程》本文将深入探讨这一实践,从连接配置到复杂空间查询操作,包括点查询、区域范围查询以及空间关系判断等,全方位展示如何在Java环... 目录前言一、相关技术背景介绍1、评价对象AOI2、数据处理流程二、对AOI空间范围查询实践1、空间查

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索