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:
- Given $$$m$$$, compute the sum over all $$$a_i$$$ such that $$$i$$$ is a submask of $$$m$$$;
- 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?
If i'm not mistaken, described implementation of the second query actually increases only $$$m$$$, not all submasks of $$$m$$$.
For example, suppose next queries:
$$$n = 3$$$
add 1 to all submasks of $$$m = 011$$$ ($$$000$$$, $$$001$$$, $$$010$$$, $$$011$$$);
compute sum over all submasks of $$$m = 101$$$ ($$$000$$$, $$$001$$$, $$$100$$$, $$$101$$$).
Your implementation increases all supermasks of $$$m = 011$$$: ($$$011$$$, $$$111$$$), so mask $$$101$$$ won't be updated.
I think you're right. Thanks, I amended the article!
For "add on submask" queries there is at least $$$O(q \sqrt{2^n n})$$$, described by tfg below.
Let's say we don't have any update. To solve it, propagate values to the submasks then propagate those propagates values to supermasks. That can be done in $$$O(2^NN)$$$ using "SOS DP".
We can use that with some "update buffer" approach. We'll keep a buffer of updates. For values outside of that buffer we can simply use the update-less approach to solve. For values inside the buffer, when we receive a query we can simply pass through the buffer and solve those in $$$O(buffer)$$$ since we can calculate the contribution of that update to that query fast by summing up 2^(popcount(updateMask & queryMask)) * updateValue. When the buffer gets bigger than some size X we use it to rebuild the information and clear the buffer, this works in $$$O(2^NN)$$$. This solution works in $$$O(2^NNQ / X + QX)$$$. This is minimized by taking something around $$$sqrt(2^NN)$$$ and results in a complexity of $$$O(Qsqrt(2^NN))$$$.
If someone wants to practice, here is a similar problem: Hackerrank — Subset
UTS Open '18 P6 — Subset Sum is a similar problem with slightly different update and more complicated query: asking for single element modification and the sum over all $$$a_i$$$ such that $$$i$$$ is a submask of $$$p$$$ and is a supermask of $$$q$$$. $$$q = 0$$$ is similar to the topic discussed in this post, which is a subtask of this UTS Open problem.
tfg solution can be applied to solve the subtask but fails for general $$$q$$$, while adamant solution can be extended to solve the full problem. They are both mentioned in the editorial.
EDIT: I forgot to mention another difference between this problem and the problem in this post. Now it is updated. tfg extends the solution to process submask addition and supermask/submask sum query, see below.
My solution can be extended to solve the full problem:
p must be a supermask of q. We can solve the problem in O(2^(popcount(q))) by using inclusion-exclusion easily. Now, if q has more than N/2 bits then we flip all bits and the problem turns into: submasks of q'=~q and supermasks of p'=~p. If q has more than N/2 bits, p also has more than N/2 and p' has less than N/2 bits so can simply use the same solution.
That solves the offline part of my solution. For the online part the number of masks is simply 2^(popcount(p & updateMask & bitwise not q)) while being 0 if updateMask & q isn't q.
Complexity is the same. Is this one of the solutions in the editorial? Edit: I opened the problem, it's slightly different because in the problem you linked updates are point updates instead of submask updates.
I think you are right.
This extends the solution to process submask addition and supermask & submask query, with $$$O(\sqrt{2^N \cdot N})$$$ per query.
I noticed that forgot to mention another difference between the UTS Open problem and the problem in this post: the UTS Open problem is asking to process single element modification while the problem in this post is asking to process single element addition. I'll edit my post.
Single element modification can be easily processed, and submask addition can be handled by computing total contribution of the queries. Is it possible to process submask modification?
Today I stumbled across Longest beautiful subsequence IZhO 2017. The solution for it also uses square root decomposition on the bits, so a very similar technique. You need to basically make a data structure that handles:
The operations can be done in $$$O(2^{n/2})$$$ each, using $$$O(2^n n)$$$ memory.