Introduction

I recently came across this problem which required an interesting trick to compute $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$$$ for all $$$1 \le i \le n - w + 1$$$ in $$$O(n)$$$ time and space. I found the trick very interesting, so I decided to write a short blog about it.

Problem

Given an array $$$a$$$ of size $$$n$$$ and an integer $$$w$$$. You are required to compute the value of $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1}$$$ for all $$$1 \le i \le n - w + 1$$$ in $$$O(n)$$$ time and space. $$$\otimes$$$ is a binary operation that is commutative ($$$x \otimes y = y \otimes x$$$) and associative ($$$(x \otimes y) \otimes z = x \otimes (y \otimes x)$$$).

Solution

Split array $$$a$$$ into blocks of size $$$w$$$. In each block, we calculate applying the operator on each prefix and on each suffix. Then, any range of width $$$w$$$ can be formed by combining the suffix of one block with the prefix of another block.

The implementation is very easy as well. Let $$$p_i = a_{\left\lfloor\frac{i - 1}{w}\right\rfloor\cdot w + 1} \otimes \ldots \otimes a_i$$$ and $$$s_i = a_i \otimes \ldots \otimes a_{\left\lceil\frac{i}{w}\right\rceil\cdot w}$$$ for all $$$1 \le i \le n$$$. Then, $$$a_i \otimes a_{i + 1} \otimes \ldots \otimes a_{i + w - 1} = s_i \otimes p_{i + w - 1}$$$.

Extension

If we try to generalize this solution to work for queries of arbitrary width, we will realize that it becomes a disjoint sparse table. In disjoint sparse table, the queries can have arbitrary width, so we need to split into blocks of width $$$2^k$$$ for all $$$1 \le k \le \log_2 n$$$. For our application, since we only have queries of a fixed width, we only need one layer, and hence we can obtain a solution in linear time and space.