Hash table vs range query
Each data structure has associated costs and benefits. In practice, it is hardly ever
true that one data structure is better than another for use in all situations. If one
data structure or algorithm is superior to another in all respects, the inferior one
will usually have long been forgotten.
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
→ Hash tables are good for doing a quick search on things.
In data structures, a range query consists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array.
→ Range queries can be used to solve Range Min/Max & Sum Queries and Range Update Queries in O(log n) time.
Data Structures and Algorithm Analysis in C++, Third Edition (Dover Books on Computer Science)
Data Structures and Algorithm Analysis in C++, Third Edition (Dover Books on Computer Science) - Kindle edition by…