Range Queries

A range query consists of a Range and a Query.

Range: specifies a lower bound value and an upper bound value (for e.g. 5 to 10 is a range).

Query: Any operation, for e.g. Add, Subtract, Multiply, Divide, Min, Max, etc.

A Range Query provides a range i.e. a lower bound and an upper bound. This range corresponds to the indices of array. For e.g., suppose we have an array, say input[], and a range, say 5 to 10, then this range specifies to consider all the numbers of array input[] from index 5 to index 10 (inclusive). Considering all the numbers in the given range there can be any query fired on that range, for e.g. sum of all numbers in array in the given range or minimum number among the numbers in array in the given range, etc.

Problem Statements Involving Range Query will be similar to:

Q.: Given an array and a range, print sum of all numbers in array in the given range. (Consider array indexing starts at 0)

Input: 

input[10] = { 10, 20, 15, 30, 5, 50, 2, 1, 100, 4 }

Range: 2 to 5

Output: 

Sum of all numbers in the range 2 to 5 = 100 

(Since input[2] + input[3] + input[4] + input[5] = 15 + 30 + 5 + 50 = 100)

Range Queries are very popular in online coding competitions, also they are useful in solving real-world problems as well. If you are into competitive coding, you'll probably come across problems involving range queries very often. There are many approaches for answering range queries efficiently and they are all simple to implement. I'll discuss all of them in my later posts. Till then, Happy Coding! 😃