Array | Range Queries

The array range query problem can be defined as follows:

Given an array of numbers, the array range query problem is to build a data structure that can efficiently answer queries of a particular type mentioned in terms of an interval of the indices.

The specific query can be of type – maximum element in the given range, most frequent element in the given range or queries like these.

Types of Array Range Queries:

Array range queries can be classified based on the type of input provided and on the type of output:

Based on the type of input:

• The value of interest is completely determined by the problem, in this case, the query consists of only a range of indices.
• A single value of interest is provided in the query.
• The query consists of a threshold where all the values above or below the threshold are of interest.
• The query consists of an exact threshold value.

Based on the type of output:

• Returns a single value matching the criteria.
• Index of an element that matches the criteria provided in the query.
• A list of all values that satisfy the given criteria.
• Only a response like “yes” or “no” denoting if there is any result matching the criteria of the query.

Some practice problems on Array range Queries:

• Easy:
  1. Range sum queries without updates
  2. Range Queries for Frequencies of array elements
  3. Range LCM Queries
  4. Count Primes in Ranges
  5. Queries for number of distinct elements in a subarray
  6. Mean of range in array
  7. Check in binary array the number represented by a subarray is odd or even
  8. Total numbers with no repeated digits in a range
  9. Queries for counts of array elements with values in given range
  10. Queries for decimal values of subarrays of a binary array
  11. GCDs of given index ranges in an array
  12. Queries on probability of even or odd number in given ranges
• Intermediate:
  1. Difference Array | Range update query in O(1)
  2. Range sum query using Sparse Table
  3. Number of indexes with equal elements in given range
  4. Constant time range add operation on an array
  5. Number whose sum of XOR with given array range is maximum
  6. Number of primes in a subarray (with updates)
  7. Print modified array after executing the commands of addition and subtraction
  8. Sum of Interval and Update with Number of Divisors
  9. Queries on XOR of greatest odd divisor of the range
  10. Print modified array after multiple array range increment operations
  11. Binary array after M range toggle operations
• Hard:
  1. Sparse Table
  2. MO’s Algorithm
  3. Sqrt (or Square Root) Decomposition Technique | Set 1 (Introduction)
  4. Range Minimum Query (Square Root Decomposition and Sparse Table)
  5. Number of elements less than or equal to a given number in a given subarray
  6. Number of elements less than or equal to a given number in a given subarray | Set 2 (Including Updates)
  7. Array range queries over range queries
  8. Array range queries for searching an element
  9. Maximum Occurrence in a Given Range
  10. Merge Sort Tree for Range Order Statistics
  11. Count and Toggle Queries on a Binary Array
  12. Min-Max Range Queries in Array
  13. Range Query on array whose each element is XOR of index value and previous element
  14. Count elements which divide all numbers in range L-R
  15. Queries for GCD of all numbers of an array except elements in a given range
  16. XOR of numbers that appeared even number of times in given Range

Quick Links :

• ‘Practice Problems’ on Arrays
• ‘Quizzes’ on Arrays
• ‘Video Tutorials’ on Arrays