Prerequisites

The main idea comes from the sliding window technique. Suppose you have q queries where every query has a fixed length (r - l) = k. You can answer each query by combining information from two blocks of size k-1 use the suffix v left block and the prefix right block. Then, you can compute the ans using those two values.

Here n = 12, k = 4, and one of the queries is: l = 6, r = 9

So, we create prefix and suffix blocks of size 3. Then, we can computed information from these two blocks to answer the query in O(1).