Range Queries
Learn Range Queries (Arrays, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
What is a Range Query? A range query asks a question about a sub-range [l, r] of an array - "what's the sum?", "what's the minimum?", "how many elements are ≥ x?" - and it usually needs to be answered MANY times over the same array. The right data structure depends on whether the array changes between queries: Static array, many sum queries: Prefix Sum - O(n) build, O(1) per query. Array updated between queries, sum/min/max queries: Segment Tree or Fenwick Tree - O(log n) per update AND per query. Static array, many min/max queries (no updates): Sparse Table - O(n log n) build, O(1) per...