⚡️ Fenwick Tree держится на одном битовом трюке

Fenwick Tree, или Binary Indexed Tree, считает prefix sums за O(log n).

Вся магия в операции:

i & -i

Она находит младший установленный бит числа.

Почему это работает?

В two’s complement число -i получается как инверсия битов i плюс 1.
Когда мы делаем i & -i, остаётся только самый правый бит, равный 1.

Например:

i = 12        // 1100
-i            // 0100 в нужной маске
i & -i = 4

Именно это значение говорит Fenwick Tree, на сколько нужно прыгнуть по индексам.

Для обновления:

for (; i < MAXN; i += i & -i)
    tree[i] += v;

Мы идём вверх по структуре и обновляем все узлы, которые покрывают этот индекс.

Для запроса суммы:

for (; i > 0; i -= i & -i)
    s += tree[i];

Мы идём вниз и собираем нужные блоки суммы.

Одна и та же операция управляет двумя направлениями:

* i += i & -i — перейти к следующему ответственному узлу
* i -= i & -i — убрать последний блок из prefix sum

Поэтому Fenwick Tree такой компактный:
никаких явных рёбер, указателей и рекурсии. Только массив и битовая арифметика.

Красота структуры в том, что дерево как бы спрятано внутри двоичного представления индекса.

⚡️ Linux может освободить RAM, не уничтожая сам диапазон виртуальной памяти процесса.

Это как раз то, что делает madvise(MADV_DONTNEED) для anonymous mappings.

Сценарий такой:

char *region = mmap(NULL, GB,
                    PROT_READ | PROT_WRITE,
                    MAP_PRIVATE | MAP_ANONYMOUS,
                    -1, 0);

// потрогали часть страниц

madvise(region, GB, MADV_DONTNEED);

После madvise виртуальные адреса остаются валидными. Процесс всё ещё «видит» тот же диапазон памяти.

Но физические страницы, которые стояли за этим диапазоном, ядро может забрать обратно. То есть адресное пространство осталось, а реальная RAM освободилась.

При следующем обращении к этому участку процесс получит свежие zero-filled страницы. Старых данных там уже не будет.

Почему это полезно:

* можно держать большой виртуальный регион без постоянного удержания RAM
* аллокаторы могут возвращать неиспользуемые страницы ядру
* long-running процессы меньше раздувают RSS
* память можно переиспользовать без полного munmap и нового mmap

Важная деталь: MADV_DONTNEED не означает «удали адреса». Это скорее сигнал ядру: «эти страницы мне сейчас не нужны, можешь забрать физическую память».

Адреса остаются. Страницы уходят. Следующее чтение приносит нули.

🖥 C++26 закрывает одну из самых больных тем lock-free кода - безопасное удаление памяти.

Проблема не в atomics.

Проблема в том, что один поток уже убрал узел из структуры, а другой всё ещё может его читать.

Удалишь слишком рано, получишь use-after-free.

Поэтому в C++26 стандартизируют Hazard Pointers.

Идея простая:

поток заранее помечает объект как “я сейчас его читаю”.

Пока хотя бы один reader держит такой hazard pointer, объект нельзя удалять.

Удаление откладывается до момента, когда все читатели закончат работу.

Это делает lock-free структуры вроде стеков, очередей и списков намного безопаснее.

Lock-free программирование становится не магией, а чуть более нормальным инженерным инструментом.

🖥 Большинство “простых” shuffle-алгоритмов дают кривой рандом

Частая ошибка:

for (int i = 0; i < n; i++) {
    int j = rand() % n;
    swap(a[i], a[j]);
}

На вид всё нормально: каждый элемент случайно меняется местами с другим.

Но проблема в вероятностях.

Для массива из n элементов существует n! перестановок.

Хороший shuffle должен давать каждой перестановке одинаковый шанс.

Наивный вариант делает n шагов, и на каждом шаге выбирает индекс из полного диапазона 0..n-1.

В итоге некоторые перестановки появляются чаще других.

Правильный подход - Fisher-Yates shuffle:

for (int i = n - 1; i > 0; i--) {
    int j = random(0, i);
    swap(a[i], a[j]);
}

Идея простая:

на каждом шаге мы выбираем элемент только из ещё не зафиксированной части массива.

Сначала выбираем последний элемент из всего массива.
Потом предпоследний - из оставшихся.
Потом следующий - из ещё меньшего диапазона.

Так каждая перестановка получает одинаковую вероятность.

В C++ лучше не писать через rand() % n, потому что там может быть ещё и modulo bias.

Нормальный вариант:

std::mt19937 rng(std::random_device{}());

for (int i = n - 1; i > 0; --i) {
    std::uniform_int_distribution<int> dist(0, i);
    int j = dist(rng);
    std::swap(a[i], a[j]);
}

Shuffle - хороший пример, где код может выглядеть “рандомным”, но математически быть неправильным.

✔️ curl - один из самых недооценённых проектов в истории софта.

Первый релиз вышел 20 марта 1998 года. Его запустил один разработчик - Daniel Stenberg.

Прошло больше 27 лет, а он всё ещё поддерживает проект.

Сегодня curl работает на миллиардах устройств и поставляется почти везде:

* macOS
* основные Linux-дистрибутивы
* Windows 10 и новее
* серверы
* контейнеры
* embedded-системы
* CI/CD пайплайны

Ирония в том, что многие пользуются curl каждый день, даже не думая об этом.

Одна маленькая CLI-утилита стала невидимой инфраструктурой интернета.

Вот так выглядит настоящий open source: без хайпа, без миллиардных раундов, но с кодом, который держит половину мира.