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 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.
Nice one! Now solve Triangle ignore the 1.5s timelimit, solve for 1s
Ok time to add something meaningful to the conversation.
Although the trick detailed can be easily dismissed as unrolled queue-like undoing, the problem linked poses the same question but for 2D spaces. And so I would like to detail this scaling:
The trick here, which can be applied in the 2D case, is to assign some reference points for which we will calculate some information which will be necessary and sufficient for completing an entire query. For triangles, given an interiour reference point, we can divide the triangle by drawing lines parallel to the axis through the given reference point, and as such we divide our query to require only information for a: trapeze in NW/SE quadrants, simple cornered triangle in NE, and rectangle in SW, all computable in linear time wrt the dimensions required for a query, which is of the order of $$$k^2$$$ (sufficiency?)
Furthermore, to assure the necessity? of the construction, we can calculate only for gridpoints which have both their coordinates divisible by $$$\frac{k}{2}$$$; as such, any query has a reference point within it.
The complexity is, therefore, clearly linear.
Uhhh, if your answers are denoted by $$$b_i$$$, then $$$b_{i+1} = b_i \otimes a_i \otimes a_{i+w}$$$, end of topic...
You should think about presenting a better showcase example. I reread the first paragraph a few times cause I was not expecting red to write a blog on a problem even a grey should be able to solve. It's not particularly educative that way and you will get "overcomplicated nonsense" rather than "clever technique" reactions even though your trick generalize to nontrivial problems
Btw this trick is in some sense a disguised divide and conquer (which would even be linear if we do not compute info about segments longer than w)
EDIT: Uhh, I was under a strong impression that you are considering XOR only, but it seems your intention was to denote an arbitrary commutative and associative binary operator with it. First thing — you do not need commutativity at all. Second thing — sparse table? I don't see any resemblance to a sparse table here. But to segment tree — surely. Or you can go with already mentioned D&C
dont you assume invertibility (and specifically, the operator being its own inverse)? i dont believe thats one of the axioms
your example doesnt solve if the operator was bitwise and for instance
I misunderstood the intention (edited my comment already)
You don't need comutativity. The way you describe the query, what $$$s_i$$$ and $$$p_i$$$ mean makes comutativity not be required.
Oh right. Thanks
How do you use it to solve the original problem?
Using bitset. :)
Build a boolean table $$$B$$$ of size $$$n\times n$$$ where $$$B_{ik}=1$$$ if and only if $$$p_i < p_{i+k}$$$. Then the number of suitable indices $$$j$$$ for a fixed $$$i$$$ is the number of ones in the bitwise $$$\texttt{AND}$$$ of the rows $$$B_i, B_{i+1}, \ldots , B_{i+m-1}$$$. You can find it for all $$$i$$$ using the approach in this blog.
In fact, this can be pushed a bit further, to obtain a structure of size O(n) that computes any sum in O(α(n)) time. See https://arxiv.org/abs/2406.06321.
Well-known in Krasnoyarsk
Another way of thinking about it is by trying to simulate a queue with 2 stacks. Then you maintain prefix / suffix aggregated values starting from the bottom of each stack so that queries can be answered with a single merge of the two top values.
It's also quite cool that this can be done in worst case $$$O(1)$$$ per insertion / window movement, by doing the "slow stack movement" in advance. A paper that roughly describes the idea and some additonal things can be seen here.
In Argentina we call this "Hugo DP", I wrote a blog about it once
bro trying really hard to get back to top 1 contributor