Предположим, у нас есть множество элементов , и каждый элемент ограничен сверху числом . Другими словами, для каждого выполняется
Существует много способов хранить такое множество, например:
std::arraystd::vectorstd::setУ каждого из них есть свои преимущества. Например, некоторые позволяют быстро вставлять и удалять элементы, тогда как другие поддерживают операции вроде lower_bound за .
Но что, если мы хотим выполнять такие операции, как:
Можно ли сделать эти операции быстрее?
Начнём с простой реализации на основе массива.
Операции, которые нам нужны:
Первые три операции легко реализуются за :
Однако объединение работает медленнее. Чтобы вычислить объединение двух множеств, нам нужно просканировать все позиции, что занимает времени.
Заметьте, что массив хранит только 0 или 1.
Поэтому вместо хранения одного целого числа на элемент мы можем упаковать много значений в биты целого числа.
Например, мы можем разбить массив на блоки размера .
Каждый блок можно хранить как unsigned long long.
Пусть -й блок — это b[i]. Тогда -й бит блока равен 1 тогда и только тогда, когда элемент
принадлежит множеству.
Это даёт следующую реализацию:
Теперь операция объединения работает с блоками вместо отдельных элементов, поэтому она занимает всего
времени.
Так что по сравнению с версией на массиве мы на практике выигрываем примерно в раза.
Вместо того чтобы писать собственную структуру, мы часто можем использовать стандартный контейнер C++:
Он реализует ту же основную идею и напрямую поддерживает многие полезные битовые операции.
Set, реализованная с помощью битовых блоков, напишите функцию GetMin(), которая возвращает минимальный элемент множества. Сделайте то же самое для GetMax(). Требуемая сложность — .GetNext(x), которая возвращает наименьший элемент, больший чем x. Требуемая сложность — .struct Set {
int a[X];
Set() {
for (int i = 0; i < X; i++) {
a[i] = 0;
}
}
void Insert(int x) {
a[x] = 1;
}
void Erase(int x) {
a[x] = 0;
}
bool Check(int x) {
return a[x];
}
};
struct Set {
...
void Union(Set T) {
for (int i = 0; i < X; i++) {
if (T.Check(i)) {
Insert(i);
}
}
}
};
struct Set {
int X;
vector<unsigned long long> b;
Set(int X_) : X(X_), b(X / 64 + 1, 0) {}
void Insert(int x) {
b[x / 64] |= (1ULL << (x % 64));
}
void Erase(int x) {
if (Check(x)) {
b[x / 64] ^= (1ULL << (x % 64));
}
}
bool Check(int x) {
return (b[x / 64] & (1ULL << (x % 64))) != 0;
}
void Union(const Set& T) {
for (int i = 0; i <= X / 64; i++) {
b[i] |= T.b[i];
}
}
};
std::bitset