About two months ago I invented this (probably well known though) when trying to solve problem that I made. Haven't seen any blogs on this, so decided to make one.
Main idea is that we can use meet-in-the-middle here.
In an naive algorithm to insert a value or erase a value, we will create a vector of size $$$2^k$$$, where $$$dp_{mask}$$$ denotes how many elements with such mask are there, and just do $$$dp_{mask}++$$$ (or do $$$dp_{mask}--$$$), so it will take $$$O(1)$$$ time, and to make a query we will iterate over all submasks of $$$mask$$$ in $$$O(2^k)$$$. It seems obvious that we can balance this.
So we can split bits in half, to add a value or erase it we will iterate over all UPmasks (in UPmask, we are replacing some zeroes with ones) of the first half of the bits (name it $$$maskup$$$) and add the second half here (name it $$$masksec$$$), so do $$$dp_{maskup+masksec}++$$$ (in case we want to add a value, but if we want to erase, substract one).
To make a query we will do an inverse of that: first half is fixed, and we iterate over all SUBmasks of the second one.
The only issue here is that we still use $$$O(2^k)$$$ memory, we can have map or unordered_map, but that's pretty slow, or alternitevly some clever of vectors.
Comments (0)
