Динамический двоичный подъем на слоях (SBLD) для запросов на отрезках
Изначально у меня была идея сделать многослойную декомпозицию, где на первом слое блоки имеют размер $$$(\sqrt{N})$$$, на втором —
Unable to parse markup [type=CF_MATHJAX]
) и так далее. Думал, что получится интересная альтернатива стандартным подходам. Но когда начал изучать архивы 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, это было очень трудно))))
