Hi everyone!

There was once a problem named "Easy When You Know How". Unfortunately, I can't remember the contest it originated from.

You're given an array $$$a_0, a_1, \dots, a_{2^n-1}$$$. Answer $$$q$$$ queries that are:

1. Given $$$m$$$, compute the sum over all $$$a_i$$$ such that $$$i$$$ is a submask of $$$m$$$;
2. Given $$$m$$$ and $$$c$$$, add $$$c$$$ to all $$$a_m$$$.

Constraints were along the lines of $$$2^n, q \leq 10^5$$$.

I tried to find anything about this technique on Codeforces, but failed, so I thought it'd be nice to write a brief blog about this cute problem.

The problem is indeed simple if you know how to solve it. The solution utilizes square root decomposition and looks as follows:

Let $$$k = \lfloor \frac{n}{2} \rfloor$$$ and $$$b_0, b_1, \dots, b_{2^{n}-1}$$$ be an array such that $$$b_{x+2^k y}$$$ is a sum of $$$a_{x+2^k y'}$$$ over all possible submasks $$$y'$$$ of $$$y$$$.

Now, to answer queries, let $$$m=x + 2^k y$$$.

• The answer to the first query is a sum of $$$b_{x'+2^k y}$$$ over all submasks $$$x'$$$ of $$$x$$$.
• For the second query one has to add $$$c$$$ to $$$b_{x+2^k y'}$$$ for all supermasks $$$y'$$$ of $$$y$$$ (i. e. all $$$y'$$$ s.t. $$$y$$$ is a submask of $$$y'$$$).

This allows to solve the problem in $$$O(2^{\lceil n/2 \rceil}q)$$$. I wonder if there are any better ways to solve it?