### Динамический двоичный подъем на слоях (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}$:↵
↵
```text↵
Слой 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 = \min(\text{ctz}(cur\_l), \; 31 - \text{clz}(R - cur\_l)) - 1$$↵
↵
Если $i < 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)↵
↵
```cpp↵
#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, это было очень трудно))))
↵
Изначально у меня была идея сделать многослойную декомпозицию, где на первом слое блоки имеют размер $(\sqrt{N}\)$, на втором — $(\sqrt{\sqrt{N}}\
↵
В итоге я решил отказаться от корней и посмотреть в сторону степеней двойки, но не через Sparse Table (который не поддерживает обновления и требует много памяти), а через фиксированную сетку слоев, совмещенную с логикой двоичного подъема. Назвал эту штуку SBLD (Segment Binary Lifting Data-structure). Получился гибрид, который выполняет запросы и точечные обновления за $2 \log N$) действий в худшем случае, используя строгие O(N) памяти (ровно 2N элементов вместе с базовым массивом).↵
↵
### Устройство сетки слоев↵
↵
Структура не хранит все пересекающиеся отрезки. Массив разбивается на независимые блоки на каждом слое `i`, где длина блока равна $2^{i+1}$:↵
↵
```text↵
Слой 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 = \min(\text{ctz}(cur\_l), \; 31 - \text{clz}(R - cur\_l)) - 1$$↵
↵
Если $i < 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)↵
↵
```cpp↵
#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, это было очень трудно))))
