Range Queries

There are ample scenarios in daily software routines where we want to execute a query over a range. Unlike executing a query simply over two elements which take O(1) time, query over a range of n elements in general will take O(n) time. High frequency of such queries could hamper the performance of the codebase. There are techniques which more or less involve pre-computation that can help us execute a range query over n elements in O(1) or O(log n) time. Obviously there could be high time complexity involved with updates over these pre-computed structures.

On a high level, we can club such scenarios into four broad categories:

• Single query, Single update

• Range query, Single update

• Single query, Range update

• Range query, Range update

• First use case is trivial and does not require any special structures

• Second and Third use case can be dealt with Segment Trees ( all time ), Fenwick Tree ( not always ), Prefix Array ( not always ), pre-computation array ( most of the times )

• Last use case can be handled efficiently using lazy propagation

• We can have in 2 dimensional segment trees for rectangular subarrays, the idea can be extended to n dimensions

• There are also concepts of lazy updates, persistant segment trees, dynamic segment trees which help in making code time efficient based on various use cases.