There’s an interesting data structure called the sqrt-tree (you can read about it here). I’ve searched everywhere but couldn’t find an implementation that supports range update queries. I would be very grateful if anyone could share their code.

Is it possible to answer these queries using bitwise Gaussian Elimination in $$$O(\log{}(maxn))$$$ complexity?

• $$$add(x)$$$ — Add number $$$x$$$ to set $$$S$$$.
• $$$order(x)$$$ — Let, $$$X$$$ denote the sorted set of all possible xor-sums of elements from a subset of $$$S$$$. Find a maximum $$$k$$$ such that $$$x\ \ge\ k$$$-th element in $$$X$$$.

I always had trouble choosing a font and a week after I found some good font I wanted to change it again. Please recommend some good monospace fonts.

Достаточно часто в программировании появляется необходимость использовать структуру данных поддерживающую операции добавления элемета, поиска минимума и удаления минимума. В C++ для этого есть несколько решений. Самый популярные из них это std::multiset и std::priority_queue, и менее известное __gnu_pbds::priority_queue (Как и всё из __gnu_pbds поддерживается только в GNU C++. Для использования этой структуры необходимо добавить #include <ext/pb_ds/priority_queue.hpp> в программу).

Давайте кратко рассмотрим что из себя представляют эти структуры.

std::multiset — структура данных хранящая элементы в отсортированном порядке. Отличается от std::set возможностью хранить несколько вхождений равных элементов. Кроме интересных нам возможностей добавлять элемент, а также получать и удалять минимум, структура поддерживает возможность удаления любого элемента по значению и итератору, поиск следующего и предыдущего элемента, а также бинарный поиск. Все описанные операции выполняются за $$$O(\log{n})$$$.

std::priority_queue — структура данных поддерживающая добавление элемента и удаление минимума за $$$O(\log{n})$$$, а получение минимума за $$$O(1)$$$. Она не поддерживает остальные описанные для std::multiset операции, но операции которые эта структура поддерживает выполняются ей быстрее чем их выполняет std::multiset.

__gnu_pbds::priority_queue — намного более гибкий аналог std::priority_queue. Может очень сильно меняться в зависимости от выбранного тега. О самой структуре и тегах можно почитать здесь. Для тегов __gnu_pbds::priority_queue я использовал сокращения (BHT = binary_heap_tag, PHT = pairing_heap_tag, BiHT = binomial_heap_tag, RCBiHT = rc_binomial_heap_tag, THT = thin_heap_tag).

Все тесты будут проведены на Codeforces на G++20 (64 bit). Для данных типа int тесты будут проведены на 2 разных задачах. Также будет сравнение производительности на задаче связанной с поиском потока минимальной стоимости. Там рассматриваемые структуры будут применяться с std::pair<long long, int>. При работе с типом int не были рассмотрены почти все теги так как все они кроме двух работают с ним совсем медленно. Перейдем к результатам тестов.

Добавление всех элементов, а после доступ к минимумам и их удаление пока структура не пуста. Псевдокод:

while (q.size() != N):
  q.push(rand())
while (q.size() != 0):
  q.top()
  q.pop()

Результат:

Равновероятный вызов доступа к минимуму и его удаления или добавления двух элементов. Псевдокод:

for (i < N):
  if (rand() % 2):
    q.push(rand())
    q.push(rand())
  else:
    q.top()
    q.pop()

Результат:

Поиск потока минимальной стоимости.

Результат:

В итоге std::priority_queue работает быстрее остальных структур во всех проведенных мной тестах. std::multiset является намного более гибкой структурой и поддерживает множество операций, но работает довольно медленно во многих случаях. __gnu_pbds::priority_queue в зависимости от тега может работать примерно также быстро как и std::priority_queue, а может работать намного медленнее с типами int и std::pair<long long, int>.