Submask range queries

Revision en1, by adamant, 2022-06-13 01:34:31

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_i$$$ such that $$$i$$$ is a submask of $$$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?

Tags submasks, range query, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English adamant 2022-06-14 00:52:40 34 Tiny change: 'to all $a_i$ such that $i$ is a submask of $m$.\n\nCon' -> 'to all $a_m$.\n\nCon'
en1 English adamant 2022-06-13 01:34:31 1337 Initial revision (published)