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.