Я придумал это около двух месяцев назад (хотя это скорее всего хорошо известная структура), когда пытался решить задачу, которую я и придумал. Я не видел ни одного блога на эту тему, поэтому решил написать свой.
Основная идея здесь это применение meet-in-the-middle.
В наивном алгоритме, для вставки, или удаления, мы просто создадим вектор размера $$$2^k$$$, где $$$dp_{mask}$$$ означает количество элементов с данным значением, и просто сделаем $$$dp_{mask}++$$$ (либо $$$dp_{mask}--$$$), поэтому это зайтем $$$O(1)$$$ времени, и чтобы сделать запрос просто пробежимся по всем подмаскам of за $$$O(2^k)$$$. Довольно очевидно, что мы можем это сбалансировать.
Разделим биты пополам, для вставки, или удаления, мы пробежимся по всем надмаскам первой половины бит (назовем $$$maskup$$$) и добавим сюда вторую половину (назовем $$$masksec$$$), то есть сделаем $$$dp_{maskup+masksec}++$$$ (либо, если хотим удалить, отнимем единицу).
Чтобы сделать запрос, сделаем наоборот: первая половина зафиксирована, и мы пробежимся по всем подмаскам второй половины.
Единственная проблема это то, что у нас осталось $$$O(2^k)$$$ памяти, мы можем сделать map или unordered_map, но это довольно медленно, или по-умному использовать векторы.
Комментарии (0)
