By adamant, history, 18 months ago,

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$.

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?

• +105

| Write comment?
 » 18 months ago, # |   +18 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.
•  » » 18 months ago, # ^ |   +5 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.
 » 18 months ago, # | ← Rev. 3 →   +5 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))$.
 » 18 months ago, # |   +8 If someone wants to practice, here is a similar problem: Hackerrank — Subset
 » 18 months ago, # | ← Rev. 2 →   +13 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.
•  » » » 18 months ago, # ^ |   0 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?
 » 18 months ago, # |   +3 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: Given $i$ and $v$, $a_i := \max(a_i, v)$ Given $b$ and $k$, find the maximum value of $a_i$, such that $\text{popcount}(i\ \text{AND}\ b) = k$ The operations can be done in $O(2^{n/2})$ each, using $O(2^n n)$ memory.