How to solve competitive programming questions with ‘Queries’?

Many questions in competitive programming are based on update and find queries.

For e.g. given an array of N elements and Q queries. Each query has L and R and you need to print the minimum array element from a[L] to a[R]. N = 10^5, Q = 10^5, 1 <= L <= R <= N. If you do it naïve it way, it would take O(N*Q) which would give TLE.

Basically, there are two types of approaches for solving such type of questions.

Online approach:

You just print the answer for each query instantaneously in the order they appear in input.

Offline approach:

You input and store all queries, sort them according to some comparison function, solve all in sorted order, output answer for all queries in order they appear in input.

Online approaches:

• PreOrder Array:

Create another array pre[] , where pre[i] stores information about [0,i]

For eg, you need range sum from L to R in each query quickly.

Solution: Create preorder array, where pre[i] = sum from 0 to i = pre[i-1] + a[i]

So, for each query, answer = pre[R] – pre[L-1].

But this is a static structure and it doesn’t work when you need to update array elements.

• Segment Tree: This is the most useful data structure for this type of questions.

http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://www.cse.iitk.ac.in/users/aca/lop12/slides/06.pdf

https://en.wikipedia.org/wiki/Segment_tree

https://proclubdaiict.wordpress.com/2015/01/25/segment-trees/

Segment Tree with lazy propagation: (For range update queries)

https://discuss.codechef.com/questions/38770/lazy-propagation

http://stackoverflow.com/questions/11765838/how-to-implement-segment-trees-with-lazy-propagation/30622980#30622980

• Binary Indexed Tree/Fenwick tree :

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

http://www.sanfoundry.com/java-program-implement-fenwick-tree/

http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

• Square Root Decomposition :

http://www.quora.com/How-does-the-technique-of-sqrt-N-decomposition-work-and-in-what-kind-of-problems-is-it-useful

• Disjoint Set Union :

https://proclubdaiict.wordpress.com/2015/06/11/disjoint-set-data-structure/

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Offline Approaches:

• Reverse Process Queries:

Process queries in from last to first. For example, if query is to delete something, solving queries in reverse order, it becomes insert instead of delete. This approach helps when inverse operation is easier to process then normal query operation.

https://www.codechef.com/MARCH15/problems/MTRWY (Do read editorial for it.)

• Sorting queries based on their ‘R’. R = right end of range query (L,R)

Question: http://www.spoj.com/problems/DQUERY/

Solution: http://codeforces.com/blog/entry/8962

• Mo’s Algorithm:

http://blog.anudeep2011.com/mos-algorithm/