Динамический двоичный подъем на слоях (SBLD) для запросов на отрезках

Изначально у меня была идея сделать многослойную декомпозицию, где на первом слое блоки имеют размер $$$(\sqrt{N})$$$, на втором — $$$(\sqrt{\sqrt{N}})$$$ и так далее. Думал, что получится интересная альтернатива стандартным подходам. Но когда начал изучать архивы Codeforces, оказалось, что про подобное уже писали, но сейчас статью не нашел.

В итоге я решил отказаться от корней и посмотреть в сторону степеней двойки, но не через Sparse Table (который не поддерживает обновления и требует много памяти), а через фиксированную сетку слоев, совмещенную с логикой двоичного подъема. Назвал эту штуку SBLD (Segment Binary Lifting Data-structure). Получился гибрид, который выполняет запросы и точечные обновления за $$$2 \log N$$$) действий в худшем случае, используя строгие O(N) памяти (ровно 2N элементов вместе с базовым массивом).

Устройство сетки слоев

Структура не хранит все пересекающиеся отрезки. Массив разбивается на независимые блоки на каждом слое i, где длина блока равна $$$2^{i+1}$$$:

 Слой 2 (len=8):  [----------------------- ans -----------------------]
 Слой 1 (len=4):  [--------- ans ---------] [--------- ans ---------]
 Слой 0 (len=2):  [--- ans ---] [--- ans ---] [--- ans ---] [--- ans ---]
 base_a (len=1):  [ L0 ]  [ L1 ]  [ L2 ]  [ L3 ]  [ L4 ]  [ L5 ]  [ L6 ]  [ L7 ]

Суммарная память по всем слоям: $$$N/2 + N/4 + N/8 + \dots = O(N)$$$. Вместе с исходным массивом base_a (который можно считать слоем -1) выходит ровно $$$2N$$$ элементов. Построение линейное — просто попарно объединяем соседей снизу вверх.

Алгоритм запроса

Мы ищем ответ на полуинтервале $$$[L, R)$$$. Стартуем в точке cur_l = L и жадно двигаемся вправо по степеням двойки, выбирая максимально возможный шаг.

Размер шага $$$i$$$ (длина шага $$$2^{i+1}$$$) ограничен двумя факторами: 1. Выравнивание левой границы: мы можем сделать шаг на слой $$$i$$$, только если текущий индекс cur_l делится на $$$2^{i+1}$$$. Это ограничение вычисляется через __builtin_ctz(cur_l). 2. Расстояние до правой границы: чтобы не вылететь за пределы $$$R$$$, шаг должен быть $$$\le R - cur_l$$$. Это ограничение определяется старшим битом: 31 - __builtin_clz(R - cur_l).

Итоговая формула выбора слоя на текущей итерации:

Если $$$i \lt 0$$$, значит, мы не можем взять даже блок длины 2 (например, когда cur_l нечетный или остался всего 1 элемент). В этом случае берем значение напрямую из base_a и сдвигаем cur_l на 1.

Почему это работает за $$$2 \log N$$$ шагов?

Процесс можно разделить на две фазы. Сначала идет подъем: пока cur_l выравнивается, значения ctz строго растут, и шаги увеличиваются (максимум $$$\log N$$$ итераций). Затем мы упираемся в ограничение по расстоянию до $$$R$$$, и начинается спуск: куски уменьшаются, что эквивалентно разложению длины оставшегося отрезка в двоичную систему (еще максимум $$$\log N$$$ шагов).

Главное отличие и продвинутые кейсы

Важное свойство SBLD — мы всегда двигаемся строго слева направо. Классическое итеративное дерево отрезков снизу-вверх сжимает границы с двух сторон одновременно. Из-за этого на некоммутативных операциях (например, динамическое перемножение матриц на отрезке) там приходится аккуратно следить за порядком склейки аккумуляторов. В SBLD порядок операций никогда не нарушается, поэтому некоммутативные структуры работают «из коробки» за $$$O(D^3 \log N)$$$.

Также вместо одного значения в блоке можно хранить отсортированный std::vector, мержить их при построении и получить Merge Sort Tree на плоских слоях. Память составит $$$O(N \log N)$$$ без оверхеда на структуру дерева и указатели, а запросы будут работать через upper_bound за $$$O(\log^2 N)$$$.

Код на C++ (пример для матриц 2х2)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
struct Matrix {
    long long mat;
    Matrix() {
        mat = 1; mat = 0;
        mat = 0; mat = 1;
    }
};

typedef Matrix T;

T combine(const T& a, const T& b) {
    T res;
    res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;
    res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;
    res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;
    res.mat = (a.mat * b.mat + a.mat * b.mat) % MOD;
    return res;
}

const T NEUTRAL = Matrix(); 

struct SBLD {
    int n;
    int max_log;
    vector<T> base_a;
    vector<vector<T>> ans;

    SBLD(vector<T> a) {
        n = a.size();
        base_a = std::move(a); 
        max_log = (n > 0) ? (32 - __builtin_clz(n)) : 0;
        ans.resize(max_log);

        if (n == 0) return;

        ans.resize((n + 1) / 2, NEUTRAL);
        for (int i = 0; i < n; i++) {
            ans[i >> 1] = combine(ans[i >> 1], base_a[i]);
        }

        for (int i = 1; i < max_log; i++) {
            int sz = (ans[i - 1].size() + 1) / 2;
            ans[i].resize(sz, NEUTRAL);
            for (int j = 0; j < ans[i - 1].size(); j++) {
                ans[i][j >> 1] = combine(ans[i][j >> 1], ans[i - 1][j]);
            }
        }
    }

    void update(int idx, T val) {
        base_a[idx] = std::move(val);
        
        int l0 = idx >> 1;
        T left0 = base_a[l0 * 2];
        T right0 = (l0 * 2 + 1 < n) ? base_a[l0 * 2 + 1] : NEUTRAL;
        ans[l0] = combine(left0, right0);

        for (int i = 1; i < max_log; i++) {
            int cur_l = idx >> (i + 1);
            int left_son = cur_l * 2;
            int right_son = left_son + 1;
            
            T val_left = ans[i - 1][left_son];
            T val_right = (right_son < ans[i - 1].size()) ? ans[i - 1][right_son] : NEUTRAL;
            
            ans[i][cur_l] = combine(val_left, val_right);
        }
    }

    T query(int L, int R) { 
        T cur_ans = NEUTRAL;
        int cur_l = L;

        while (cur_l < R) {
            int limit_r = 31 - __builtin_clz(R - cur_l);
            int limit_l = (cur_l == 0) ? limit_r : __builtin_ctz(cur_l);
            
            int i = min(limit_l, limit_r) - 1;
            
            if (i < 0) {
                cur_ans = combine(cur_ans, base_a[cur_l]);
                cur_l += 1;
            } else {
                cur_ans = combine(cur_ans, ans[i][cur_l >> (i + 1)]);
                cur_l += (1 << (i + 1));
            }
        }
        return cur_ans;
    }
};

Конечно, стандартное итеративное ДО на массиве пишется короче и на базовых операциях вроде суммы выиграет по константе за счет симметричного сжатия границ. Но для тяжелых или некоммутативных объектов, где критически важен строгий порядок объединения слева-направо, такая явная разбивка по слоям двоичного подъема выглядит довольно нативно.

Кто-нибудь кодил подобные структуры или тестировал их производительность на реальных задачах? Интересно услышать мысли в комментариях.

Upd: урааа я не зря потратил столько времени разбираться с MathJax, это было очень трудно))))