Range-Queries: algorithms, data structures and applications

• Grant number: 16/11275-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: July 01, 2016
• End date: December 31, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Candida Nunes da Silva
• Grantee: Lucas Sampaio da Rocha
• Host Institution: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brazil

Abstract

We propose to study the \emph{range queries} problem, typically abbreviated as RSQ (\textsl{Range Sum Query}) or RMQ (\textsl{Range Min Query}), and also some variations of this problem. A comparative analysis of several algorithms and data structures used to solve each variation of the problem will be presented. The parameters used for comparison will be both theoretical, such as asymtoptic analysis, and pratical, such as running time of each algorithm when different families of entries are considered. In addition, we will also present some classic applications of this problem, which serve as motivation for its study, such as a reduction of the problem of finding the lowest common ancestor to RMQ. e sobre diversas variações do problema. Será feita uma análise comparativa de vários algoritmos e estruturas de dados que podem ser usados para resolver cada variação do problema, na qual serão comparados aspectos teóricos como complexidade assintótica e aspectos práticos como tempo de execução de cada algoritmo para diferentes famílias de entradas. Neste projeto também serão apresentadas algumas aplicações clássicas deste problema que motivam o estudo do mesmo, como uma redução do problema do menor ancestral comum (LCA, em inglês \textsl{lowest common ancestor}) para o RMQ.