There is such an implementation of the sieve of Eratosthenes:

const int N = 1e8;

bool used[N];

void solve() {
    ll sum = 0;
    for (int i = 2; i < N; i++) {
        if (!used[i]) {
            sum += i;
            for (int j = min((ll)INT32_MAX, i * 1ll * i); j < N; j += i)
                used[j] = true;
        }
    }
    cout << sum << "\n";
}

Then replace the second line with bitset used;

const int N = 1e8;

bitset<N> used;

void solve() {
    ll sum = 0;
    for (int i = 2; i < N; i++) {
        if (!used[i]) {
            sum += i;
            for (int j = min((ll)INT32_MAX, i * 1ll * i); j < N; j += i)
                used[j] = true;
        }
    }
    cout << sum << "\n";
}

For comparison, let 's take another linear sieve of Eratosthenes.

const int N = 1e8;

int le[N], primes[N / 10];

void solve() {
    ll sum = 0;
    int m = 0;
    for (int i = 2; i < N; i++) {
        if (!le[i]) {
            sum += i;
            primes[m++] = i;
            le[i] = i;
        }
        for (int j = 0; j < m && primes[j] <= le[i] && primes[j] * i < N; j++)
            le[primes[j] * i] = primes[j];
    }
    cout << sum << "\n";
}

Running time table on compiler GNU G++20 11.2.0 (64 bit, winlibs) with #pragma GCC optimize("O3") in all three solutions.

\begin{array}{|c|c|c|c|} \hline N & usual & linear & bitset \cr \hline 2e7 & 202ms & 140ms & 78ms \cr \hline 5e7 & 467ms & 374ms & 249ms \cr \hline 1e8 & 1138ms & 732ms & 686ms \cr \hline 2e8 & 2308ms & ML & 1669ms \cr \hline \end{array}

I guess it's because of the cache. The data takes up 8 times less memory and is cached better. The more cache there is on the computer, the more noticeable the acceleration. For example, I have a 3-fold acceleration on $$$N = 1e8$$$ compared to a conventional sieve.

Unfortunately, this is useless in practice, because almost always in the sieve we want to get some more information.

Мне казалось, что этого нигде нет и я придумал что-то новое, но после того как я предложил задачу на codeforces, один из координаторов сказал, что пару лет назад уже видел задачу, где использовалось что-то похожее. Поэтому задачу отклонили. Так как я не смог придумать более интересную задачу на этот трюк, я просто напишу об этом в блоге.

Задача

Пусть дана какая-то задача, которую мы умеем решать с помощью центроидной декомпозиции. Например такая. Дано дерево, в каждой вершине записано число a[i]. Поступают 2 типа запросов.

1. Даны $$$v$$$, $$$d$$$, $$$c$$$. Надо перекрасить все вершины на расстоянии не больше $$$d$$$ от $$$v$$$ в цвет $$$c$$$.

2. Дана $$$v$$$. Надо узнать цвет вершины $$$v$$$.

Теперь эта задача не на дереве, а на связном графе. Но есть одно очень интересное ограничение. m — n + 1 $$$\le$$$ 100. То есть в дерево добавили не больше 100 рёбер.

Сначала напомню как решалась задача на дереве. Мы строили дерево центроидов глубины $$$O(\log n)$$$, для каждого центроида хранили структуру, которая умела красить вершины от $$$C$$$ на расстоянии не более $$$d$$$ и узнавать цвет вершины. Эта структура называется стек, в котором хранятся тройки элементов (расстояние, цвет, время). При чем расстояние строго убывает. Тогда при покраске надо удалить некоторые элементы с конца стека и положить новый элемент. А при запросе цвета ответ можно найти бинпоиском по локальной глубине $$$v$$$.

Мы научились отвечать на запросы, если красим вершины от заданного центроида. Теперь переберем все центроиды $$$C$$$, которые являются предками $$$v$$$ в дереве центроидов и для них сделаем операции выше. Если запрос первого типа, и мы красим от $$$v$$$ на расстояние не более $$$d$$$, то от $$$C$$$ надо покрасить на расстояние не более $$$d - dist(v, C)$$$ Если мы сейчас отвечаем на запрос второго типа, то из всех цветов надо выбрать тот, у которого максимальное время. Почему это работает? Предположим, что был запрос покраски от $$$v$$$, который задел $$$u$$$, цвет которой мы хотим сейчас узнать. Тогда существует центроид $$$C = lca(v, u)$$$ в дереве центроидов. $$$C$$$ — общих центроид и для $$$v$$$, и для $$$u$$$. Причем, он находится на пути от $$$v$$$ до $$$u$$$ в исходном дереве. Тогда когда мы переберем $$$C$$$, правильный ответ нам гарантирован.

Но теперь, когда не дерево, а граф, то построить дерево центроидов нельзя. Давайте переделаем определение центроида и построим нечто похожее. get(G) будет выдавать новый центроид по следующему алгоритму:

1. Если в G есть цикл, то верни любую вершину на цикле.

2. Если G — дерево, то верни любой обычный центроид.

Еще одно изменение в постройке — это то, что теперь глубины вершин надо искать не dfs-ом, а bfs-ом. Тогда дерево новых центроидов будет выглядеть как бамбук из 100 вершин, к которому подвешено дерево обычных центроидов. Я утверждаю, что тогда алгоритм выше будет корректно работать. Опять же, пусть была покраска в $$$v$$$, которая задевает $$$u$$$ и мы хотим узнать цвет $$$u$$$. Тогда существует вершина $$$C$$$, которая является предком $$$lca(v, u)$$$ (обратите внимание, что не ровно lca, а предком lca), что крайчайший путь из $$$v$$$ в $$$u$$$ проходит через вершину $$$C$$$. И когда мы ее переберем, посчитается правильный ответ.

Обработка первого запроса амортизировано занимает $$$O(m - n + 1 + \log n)$$$, а второго $$$O((m - n + 1 + \log n) \log n)$$$.

Другие задачи

Все задачи, который я знаю и умею решать, где используются центроиды для ответа на запросы (таких не очень много), я умею обобщать на граф. Но, к сожалению, не любую задачу на дереве можно так обобщить. Например, если центроиды используются для подсчета количества путей в дереве (более точно, количество пар $$$v$$$, $$$u$$$), то здесь некоторые пути будут учитываться несколько раз, если между ними несколько крайчайших путей. Ответ, полученный таким способом дает неплохую верхнюю границу. Реальный ответ меньше не больше чем на $$$(m - n + 1)n$$$.

Спасибо andreyDagger за перевод на английский язык.